A hashgraph implemented as a spatial grid. More...

#include <ash/impl/hashgrid.h>

Inheritance diagram for ash::hashgrid:

Classes
struct	const_navigator
	The const type used to move around the grid in an arbitrary manner. More...
struct	navigator
	The type used to move around the grid in an arbitrary manner. More...
Public Types
typedef Morton	key_type
	The type of key associated with elements.
typedef Value	value_type
	The type of object stored by the container.
typedef value_type *	pointer
	Pointer to value_type.
typedef value_type const *	const_pointer
	Const pointer to value_type.
typedef value_type &	reference
	Reference to value_type.
typedef value_type const &	const_reference
	Const reference to value_type.
typedef _ASH_POINT_T< dim_cast < Morton::D >::D >	point_type
	Floating-point coordinate type.
typedef Morton	morton_type
	Interleaved coordinate type.
typedef Morton::pcoord_type	pcoord_type
	Coordinate type.
typedef equal_to< key_type >	key_equal
	The key comparison functor used by the container.
typedef KeyAccess	key_access
	Functor to access a key_type from a value_type.
typedef morton_hasher < morton_type >	hasher
	The hash functor used by the container.
typedef _Base::allocator_type	allocator_type
	The allocator used by the container.
typedef Morton::value_type	size_type
	The unsigned type used to represent the size of the container.
typedef _Base::difference_type	difference_type
	The signed type used to represent the distance between iterators.
typedef _Base::iterator	iterator
	The container's iterator.
typedef _Base::const_iterator	const_iterator
	The container's const_iterator.
typedef _Base::local_iterator	local_iterator
	The container's local_iterator.
typedef _Base::const_local_iterator	const_local_iterator
	The container's const_local_iterator.
typedef _Base::iterator_pair	iterator_pair
	A pair of iterators (convenience).
typedef _Base::const_iterator_pair	const_iterator_pair
	A pair of const_iterators (convenience).
typedef _range_itr	range_iterator
typedef _const_range_itr	const_range_iterator
typedef _path_itr	path_iterator
typedef _const_path_itr	const_path_iterator
enum	{ LINKS_PER_NODE = Node::NUM_LINKS }
Public Member Functions
void	swap (hashgraph &hg)
	Swap method.
size_type	bucket (key_type const &key) const

bool	operator== (hashgraph const &hg) const
Constructors/Destructors
We use the default copy constructor. We use the default destructor.
	hashgrid (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Default constructor.
template<class InputIterator >
	hashgrid (InputIterator const &f, InputIterator const &l, size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Iterative constructor.
Insert/Delete
pair< iterator, bool >	insert (const_reference v)
	Insert an element into the container.
template<class InputIterator >
void	insert (InputIterator f, InputIterator const &l)
	Insert a range of elements [f,l) into the container.
Navigator Methods
navigator	navigate (key_type const &key)
const_navigator	navigate (key_type const &key) const
Range-Iterator Methods
Use the normal end() method.
range_iterator	range_begin (key_type const &key, size_type range)
const_range_iterator	range_begin (key_type const &key, size_type range) const
Path-Iterator Methods
Use the normal end() method.
path_iterator	path_begin (point_type const &p1, point_type const &p2)
const_path_iterator	path_begin (point_type const &p1, point_type const &p2) const
Iterator Functions
iterator	begin ()
	Get an iterator to the beginning.
const_iterator	begin () const
	Get an iterator to the beginning.
local_iterator	begin (size_type i)

const_local_iterator	begin (size_type i) const

iterator	end ()
	Get an iterator to the end.
const_iterator	end () const
	Get an iterator to the end.
local_iterator	end (size_type i)

const_local_iterator	end (size_type i) const

Size Functions
size_type	size () const
	Get the size of the container.
size_type	max_size () const
	Get the maximum size of the container.
size_t	dynamic_memory () const
	Get the container's dynamic memory load.
size_t	memory () const
	Get the container's total memory load.
bool	empty () const
	Check if the container is empty.
size_type	bucket_count () const
	Get the number of buckets the container has.
void	resize (size_type n)
	Resize the container to hold at least n elements.
void	rehash (size_type n)

Accessor Methods
hasher	hash_funct () const
	Get the hash functor used by the container.
hasher	hash_function () const
	Get the hash functor used by the container.
key_equal	key_eq () const
	Get the key comparison functor used by the container.
Insert/Delete
void	erase (iterator pos)
	Erase an element.
size_type	erase (key_type const &k)
	Erase an element.
void	erase (iterator first, iterator const &last)
	Erase a range of elements.
void	clear ()
	Erase all elements.
Lookup
iterator	find (key_type const &k)
	Find an element.
const_iterator	find (key_type const &k) const
	Find an element.
size_type	count (key_type const &k) const
	Count the number of elements with a given key.
iterator_pair	equal_range (key_type const &k)
	Find all elements matching a given key.
const_iterator_pair	equal_range (key_type const &k) const
	Find all elements matching a given key.
Hash Container Functions
float	load_factor () const

float	max_load_factor () const

float	max_load_factor (size_type new_grow)

float	min_load_factor () const
	Get the min load factor.
float	min_load_factor (size_type new_shrink)
	Set the min load factor.
Static Public Attributes
static const DIM	D = dim_cast<morton_type::D>::D
Protected Types
typedef _Type	hashgrid_type
typedef _Base	hashgraph_type
typedef _Base::hashtable_type	hashtable_type
	The hashtable used as a backend.
typedef _Base::node_type	node_type

typedef _Base::navigator	_Base_nav
typedef _Base::const_navigator	_Base_const_nav
typedef _Base::iterator_base	iterator_base
typedef _Base::const_iterator_base	const_iterator_base
typedef grid_navigator < hashgrid, iterator_base, trivial, D >	navigator_base
typedef grid_navigator < hashgrid, const_iterator_base, add_const, D >	const_navigator_base
typedef f_access_node< Node, KeyAccess >	node_key_access
	Functor to get/set the key of a node (wrapper for key_access).
typedef table_node_allocator < allocator_type >	hashtable_allocator
	The hashtable's allocator.
typedef hashtable_type::iterator	_Ht_iterator
	The hashtable's iterator - we'll wrap it with our own.
typedef hashtable_type::const_iterator	_Ht_const_iterator
	The hashtable's const_iterator - we'll wrap it with our own.
typedef pair< _Ht_iterator, _Ht_iterator >	_Ht_iterator_pair
	A pair of the hashtable's iterators (convenience).
typedef pair < _Ht_const_iterator, _Ht_const_iterator >	_Ht_const_iterator_pair
	A pair of the hashtable's const_iterators (convenience).
Protected Attributes
key_access	access_key
hashtable_type	_M_Ht
Related Functions
(Note that these are not member functions.)
template<typename V , class M , class KA , class A , _ASH_HT_IMPL Ht>
void	swap (hashgrid< V, M, KA, A, Ht > &x, hashgrid< V, M, KA, A, Ht > &y)
	Global swap.
template<class N , typename K , class HF , class KA , class EK , class A , _ASH_HT_IMPL HT>
void	swap (hashgraph< N, K, HF, KA, EK, A, HT > &x, hashgraph< N, K, HF, KA, EK, A, HT > &y)
	Global swap.

Detailed Description

A hashgraph implemented as a spatial grid.

Template Parameters:

Value	The type of object stored. Also defined as hashgrid::value_type.
Morton	[MortonXY\|MortonXYZ] The key type associated with objects. Also defined as hashgrid::key_type.
KeyAccess	A functor to get/set the hashgrid::key_type of a hashgrid::value_type.
Alloc	The allocator type - unimplemented.
Ht	The hashtable type to use as a backend.

Note:: This is the last derivation where the stored value_type is not specified, eg. for a hashset vs. hashmap style container. A hashset-like implementation is not provided, as the key_type only determines the size of the Morton and PCoord types, and so a hashset-like implementation would not provide any way to store arbitrary data.

The PCoord and Morton classes (hashgrid::pcoord_type and hashgrid::morton_type respectively) are unions which act as abstractions for an unsigned type (hashgrid::key_type). Note that the unsigned type has the same total size as the associated PCoord and Morton types, with the bits divided equally among the coordinate components. When in doubt using a uint64 as the key_type will give you more possible coordinates than a 64-bit system can realistically hold in memory (32 bits per dimension for 2D, 21 bits per dimension for 3D). The PCoord type is basically just a bitfield - each coordinate component has a contiguous block of bits. To hash a PCoord, we interleave the bits of the coordinate components, so that each component occupies every 2nd or 3rd bit for 2D or 3D respectively. This turns the PCoord into a Morton, which is provided to deal with the interleaved version. The hashtable backend only uses the unsinged type.

The are several reasons for storing the data this way:

Interleaving the bits provides a perfect hash function - unique coord in, unique key out.
Bit-significance is preseved - all bits from each coordinate component are in the same order with respect to the rest of the component's bits. This helps to minimize collisions - if you have a full square/cube grid starting at the origin, you are guaranteed to have 0 collisions for all lookups.
Built-in parallelism - because the bits with the same significance are stored adjacent to one another, each set of 2 or 3 bits (for 2D or 3D respecively) represents a square area or cubic volume equivalent to the significance of the bits.

Member Typedef Documentation

typedef hashtable_type::const_iterator ash::hashgraph::_Ht_const_iterator [protected, inherited]

The hashtable's const_iterator - we'll wrap it with our own.

typedef pair<_Ht_const_iterator, _Ht_const_iterator> ash::hashgraph::_Ht_const_iterator_pair [protected, inherited]

A pair of the hashtable's const_iterators (convenience).

typedef hashtable_type::iterator ash::hashgraph::_Ht_iterator [protected, inherited]

The hashtable's iterator - we'll wrap it with our own.

typedef pair<_Ht_iterator, _Ht_iterator> ash::hashgraph::_Ht_iterator_pair [protected, inherited]

A pair of the hashtable's iterators (convenience).

typedef _Base::allocator_type ash::hashgrid::allocator_type

The allocator used by the container.

Reimplemented from ash::hashgraph.

typedef _Base::const_iterator ash::hashgrid::const_iterator

The container's const_iterator.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef _Base::const_iterator_pair ash::hashgrid::const_iterator_pair

A pair of const_iterators (convenience).

Reimplemented from ash::hashgraph.

typedef _Base::const_local_iterator ash::hashgrid::const_local_iterator

The container's const_local_iterator.

Reimplemented from ash::hashgraph.

typedef value_type const* ash::hashgrid::const_pointer

Const pointer to value_type.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef value_type const& ash::hashgrid::const_reference

Const reference to value_type.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef _Base::difference_type ash::hashgrid::difference_type

The signed type used to represent the distance between iterators.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef morton_hasher<morton_type> ash::hashgrid::hasher

The hash functor used by the container.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef table_node_allocator<allocator_type> ash::hashgraph::hashtable_allocator [protected, inherited]

The hashtable's allocator.

typedef _Base::hashtable_type ash::hashgrid::hashtable_type [protected]

The hashtable used as a backend.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef _Base::iterator ash::hashgrid::iterator

The container's iterator.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef _Base::iterator_pair ash::hashgrid::iterator_pair

A pair of iterators (convenience).

Reimplemented from ash::hashgraph.

typedef KeyAccess ash::hashgrid::key_access

Functor to access a key_type from a value_type.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef equal_to<key_type> ash::hashgrid::key_equal

The key comparison functor used by the container.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef Morton ash::hashgrid::key_type

The type of key associated with elements.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef _Base::local_iterator ash::hashgrid::local_iterator

The container's local_iterator.

Reimplemented from ash::hashgraph.

typedef Morton ash::hashgrid::morton_type

Interleaved coordinate type.

Interchangeable with key_type and pcoord_type for all public methods.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef f_access_node<Node, KeyAccess> ash::hashgraph::node_key_access [protected, inherited]

Functor to get/set the key of a node (wrapper for key_access).

typedef _Base::node_type ash::hashgrid::node_type [protected]

Concept: ash::hash_graph

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef Morton::pcoord_type ash::hashgrid::pcoord_type

Coordinate type.

Interchangeable with key_type and morton_type for all public methods.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef _ASH_POINT_T<dim_cast<Morton::D>::D> ash::hashgrid::point_type

Floating-point coordinate type.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef value_type* ash::hashgrid::pointer

Pointer to value_type.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef value_type& ash::hashgrid::reference

Reference to value_type.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef Morton::value_type ash::hashgrid::size_type

The unsigned type used to represent the size of the container.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

typedef Value ash::hashgrid::value_type

The type of object stored by the container.

Reimplemented from ash::hashgraph.

Reimplemented in ash::dense_hashgrid< Coord, Data, Alloc >, and ash::sparse_hashgrid< Coord, Data, Alloc >.

Constructor & Destructor Documentation

ash::hashgrid::hashgrid	(	size_type	n = `0`,
		hasher const &	h = `hasher()`,
		key_equal const &	k = `key_equal()`
	)		`[inline, explicit]`

Default constructor.

Parameters:

n	The number of expected elements.
h	The hasher object to copy, if any.
k	The key_equal object to copy, if any.

template<class InputIterator >

ash::hashgrid::hashgrid	(	InputIterator const &	f,
		InputIterator const &	l,
		size_type	n = `0`,
		hasher const &	h = `hasher()`,
		key_equal const &	k = `key_equal()`
	)		`[inline]`

Iterative constructor.

Parameters:

f	The beginning of the range to copy.
l	The end of the range to copy.
n	The number of expected elements.
h	The hasher object to copy, if any.
k	The key_equal object to copy, if any.

Member Function Documentation

iterator ash::hashgraph::begin ( ) [inline, inherited]

Get an iterator to the beginning.

Returns:: An iterator to the beginning of the container.

Concept: stl::container

Reimplemented in ash::hashlist.

const_iterator ash::hashgraph::begin ( ) const [inline, inherited]

Get an iterator to the beginning.

Returns:: A const_iterator to the beginning of the container.

Concept: stl::container

Reimplemented in ash::hashlist.

local_iterator ash::hashgraph::begin ( size_type i ) [inline, inherited]

Concept: tr1::unordered_associative_container

const_local_iterator ash::hashgraph::begin ( size_type i ) const [inline, inherited]

Concept: tr1::unordered_associative_container

size_type ash::hashgraph::bucket ( key_type const & key ) const [inline, inherited]

Concept: tr1::unordered_associative_container

size_type ash::hashgraph::bucket_count ( ) const [inline, inherited]

Get the number of buckets the container has.

Returns:: The number of currently-allocated buckets.

Concept: stl::hashed_associative_container

void ash::hashgraph::clear ( ) [inline, inherited]

Erase all elements.

Concept: stl::associative_container

size_type ash::hashgraph::count ( key_type const & k ) const [inline, inherited]

Count the number of elements with a given key.

Parameters:

key	The key to search for.

Returns:: The number of elements matching key. Because this is a Unique Associative Container , the return value will be 0 or 1.

Concept: stl::unique_associative_container

size_t ash::hashgraph::dynamic_memory ( ) const [inline, inherited]

Get the container's dynamic memory load.

Returns:: The amount of dynamic memory used by the container in bytes.

bool ash::hashgraph::empty ( ) const [inline, inherited]

Check if the container is empty.

Returns:: True if the container is empty.

Concept: stl::container

iterator ash::hashgraph::end ( ) [inline, inherited]

Get an iterator to the end.

Returns:: An iterator to the end of the container.

Concept: stl::container

Reimplemented in ash::hashlist.

const_iterator ash::hashgraph::end ( ) const [inline, inherited]

Get an iterator to the end.

Returns:: A const_iterator to the end of the container.

Concept: stl::container

Reimplemented in ash::hashlist.

local_iterator ash::hashgraph::end ( size_type i ) [inline, inherited]

Concept: tr1::unordered_associative_container

const_local_iterator ash::hashgraph::end ( size_type i ) const [inline, inherited]

Concept: tr1::unordered_associative_container

iterator_pair ash::hashgraph::equal_range ( key_type const & k ) [inline, inherited]

Find all elements matching a given key.

Parameters:

key	The key to search for.

Returns:: A pair of iterators for the range of elements [first,second). Because this is a Unique Associative Container , the first iterator points to the element, or to the end() if not found. The second iterator points to 1 past the first, or to the end().

Concept: stl::unique_associative_container

Reimplemented in ash::hashlist.

const_iterator_pair ash::hashgraph::equal_range ( key_type const & k ) const [inline, inherited]

Find all elements matching a given key.

Parameters:

key	The key to search for.

Returns:: A pair of const_iterators for the range of elements [first,second). Because this is a Unique Associative Container , the first const_iterator points to the element, or to the end() if not found. The second const_iterator points to 1 past the first, or to the end().

Concept: stl::unique_associative_container

Reimplemented in ash::hashlist.

void ash::hashgraph::erase ( iterator pos ) [inline, inherited]

Erase an element.

Parameters:

itr	An iterator pointing to the element to erase.

Concept: stl::associative_container

Reimplemented in ash::hashlist.

size_type ash::hashgraph::erase ( key_type const & k ) [inline, inherited]

Erase an element.

Parameters:

key	The key of the element to erase.

Returns:: The number of erased elements.

Concept: stl::associative_container

void ash::hashgraph::erase	(	iterator	first,
		iterator const &	last
	)		`[inline, inherited]`

Erase a range of elements.

Parameters:

f	The beginning of the range to erase.
l	The end of the range to erase.

Concept: stl::associative_container

Reimplemented in ash::hashlist.

iterator ash::hashgraph::find ( key_type const & k ) [inline, inherited]

Find an element.

Parameters:

key	The key of the element to search for.

Returns:: An iterator to the element, or to the end() if not found.

Concept: stl::associative_container

Reimplemented in ash::hashlist.

const_iterator ash::hashgraph::find ( key_type const & k ) const [inline, inherited]

Find an element.

Parameters:

key	The key of the element to search for.

Returns:: A const_iterator to the element, or to the end() if not found.

Concept: stl::associative_container

Reimplemented in ash::hashlist.

hasher ash::hashgraph::hash_funct ( ) const [inline, inherited]

Get the hash functor used by the container.

Returns:: A copy of the container's hasher object.

Concept: stl::hashed_associative_container

hasher ash::hashgraph::hash_function ( ) const [inline, inherited]

Get the hash functor used by the container.

Returns:: A copy of the container's hasher object.

Concept: tr1::unordered_associative_container

pair<iterator, bool> ash::hashgrid::insert ( const_reference v ) [inline]

Insert an element into the container.

Parameters:

obj	The element to insert.

Returns:: An iterator and a bool. The iterator points to the inserted element, or to another with the same key if one is already in the container. The bool is true if the element was inserted, and false in the case of a duplicate key.

Concept: stl::unique_associative_container

Reimplemented from ash::hashgraph.

template<class InputIterator >