The base class for dense_hashmatrix and sparse_hashmatrix. More...

#include <ash/impl/hashmatrix.h>

Inheritance diagram for ash::hashmatrix:

Classes
struct	const_iterator
	The const type used to iterate through the contents of the container. More...
struct	const_local_iterator
	The const type used to iterate through a set of elements that share a hash code. More...
struct	const_navigator
	The const type used to move around the matrix in an arbitrary manner. More...
struct	const_path_iterator
	The const type used to iterate through a group of objects along a path. More...
struct	const_range_iterator
	The const type used to iterate through a group of contiguous objects. More...
struct	iterator
	The type used to iterate through the contents of the container. More...
struct	local_iterator
	The type used to iterate through a set of elements that share a hash code. More...
struct	navigator
	The type used to move around the matrix in an arbitrary manner. More...
struct	path_iterator
	The type used to iterate through a group of objects along a path. More...
struct	range_iterator
	The type used to iterate through a group of contiguous objects. More...
Public Types
typedef _Morton	key_type
	The type of key associated with objects in the container.
typedef _Val	value_type
	The type of the object the container holds.
typedef value_type *	pointer
	The type that serves as a pointer to value_type.
typedef value_type const *	const_pointer
	The type that serves as a const pointer to value_type.
typedef value_type &	reference
	The type that serves as a reference to value_type.
typedef value_type const &	const_reference
	The type that serves as a pointer to value_type.
typedef _ASH_POINT_T< dim_cast < _Morton::D >::D >	point_type
	The type used to represent a floating-point coordinate.
typedef _Morton	morton_type
	The type used to represent a hashed/interleaved coordinate.
typedef _Morton::pcoord_type	pcoord_type
	The type used to represent a coordinate.
typedef equal_to< key_type >	key_equal
	The functor used to compare keys for equality.
typedef _KeyAccess	key_access

typedef morton_hasher < morton_type >	hasher
	The functor type used to hash keys.
typedef _Alloc	allocator_type

typedef _Morton::value_type	size_type
	The unsigned type used to represent the size of the container.
typedef sign< size_type >::type	difference_type
	The signed integral type used to represent the distance between iterators.
Public Member Functions
Iteration Methods
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

Bucket Methods
size_type	bucket (key_type const &key) const

size_type	bucket_count () const
	Get the number of buckets the container has.
size_type	max_bucket_count () const

size_type	bucket_size (size_type i) const

Size Methods
size_type	size () const
	Get the size of the container.
size_type	max_size () const
	Get the maximum size of the container.
bool	empty () const
	Check if the container is empty.
float	load_factor () const

float	max_load_factor () const

void	max_load_factor (float new_grow)

float	min_load_factor () const
	Get the min load factor.
void	min_load_factor (float new_shrink)
	Set the min load factor.
void	resize (size_type n)
	Resize the container to hold at least n elements.
void	rehash (size_type n)

size_t	dynamic_memory () const
size_t	memory () const
Lookup Methods
iterator	find (key_type const &key)
	Find an element.
const_iterator	find (key_type const &key) const
	Find an element.
size_type	count (key_type const &key) const
	Count the number of elements with a given key.
iterator_pair	equal_range (key_type const &key)
	Find all elements matching a given key.
const_iterator_pair	equal_range (key_type const &key) const
	Find all elements matching a given key.
Insertion/Deletion Methods
pair< iterator, bool >	insert (const_reference obj)
	Insert an element into the container.
template<class InputIterator >
void	insert (InputIterator f, InputIterator l)
	Insert a range of elements [f,l) into the container.
void	erase (iterator itr)
	Erase an element.
void	erase (iterator f, iterator l)
	Erase a range of elements.
void	clear ()
	Erase all elements.
Utility 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.
key_type const &	extract_key (value_type const &val) const
Constructors/Destructors
We use the default copy constructor. We use the default destructor.
	hashmatrix (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Default constructor.
template<class InputIterator >
	hashmatrix (InputIterator const &f, InputIterator const &l, size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
	Iterative constructor.
void	swap (hashmatrix &obj)

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)
	Hash-Matrix concept. ,range_begin(key_type const&,size_type)
const_range_iterator	range_begin (key_type const &key, size_type range) const
	Get an iterator to go through all elements in a given range.
Path-Iterator Methods
Use the normal end() method.
path_iterator	path_begin (point_type const &p1, point_type const &p2)
	Get an iterator from point A to point B.
const_path_iterator	path_begin (point_type const &p1, point_type const &p2) const
	Get an iterator from point A to point B.
Static Public Attributes
static const DIM	D = dim_cast<_Morton::D>::D

static const size_type	empty_key = impl::matrix_keys<_Morton>::empty_key

static const size_type	deleted_key = impl::matrix_keys<_Morton>::deleted_key

static const pcoord_type	pcoord_max

Protected Types
typedef table_value_allocator < typename _Alloc::template rebind< _Val >::other >	hashtable_allocator
typedef _Ht< value_type, key_type, hasher, key_access, key_equal, hashtable_allocator >	hashtable_type
typedef hashtable_type::iterator	hashtable_iterator
typedef hashtable_type::const_iterator	hashtable_const_iterator
typedef hashtable_type::local_iterator	hashtable_local_iterator
typedef hashtable_type::const_local_iterator	hashtable_const_local_iterator
typedef matrix_iterator < hashmatrix, hashtable_iterator, trivial >	iterator_base
typedef matrix_iterator < hashmatrix, hashtable_const_iterator, add_const >	const_iterator_base
typedef matrix_iterator < hashmatrix, hashtable_local_iterator, trivial >	local_iterator_base
typedef matrix_iterator < hashmatrix, hashtable_const_local_iterator, add_const >	const_local_iterator_base
typedef pair< iterator, iterator >	iterator_pair
	convenience
typedef pair< const_iterator, const_iterator >	const_iterator_pair
	convenience
typedef matrix_navigator < hashmatrix, iterator_base, trivial, D >	navigator_base
typedef matrix_navigator < hashmatrix, const_iterator_base, add_const, D >	const_navigator_base
Protected Attributes
key_access	access
hashtable_type	hashtable
Related Functions
(Note that these are not member functions.)
void	swap (hashmatrix &x, hashmatrix &y)
	Global swap.

Detailed Description

The base class for dense_hashmatrix and sparse_hashmatrix.

Template Parameters:

_Val	The type of value stored by the container.
_Morton	The container's key type, must be MortonXY<> or MortonXYZ<>.
_KeyAccess	The key access functor.
_Alloc	The allocator.
_Ht	The hash table to use as a backend.

A Hash Matrix is a geometric hashed container which implements the STL concepts Unique Hashed Associative Container and Pair Associative Container . As such, it has many similarities with STL's hash_map. The only area where the hash_map semantics are not valid for a hash_matrix is in the template parameters. The major difference is that you cannot specify an arbitrary key type, it must be a pcoord type. In reality you are specifying 2 things this way: the size of the key, and the dimensionality of the data (2D or 3D). Since the key type is mostly pre-defined, the hash functor and key equality functor are also built-in; you cannot specify either. As a result, there are only 3 template parameters:

The coord type (limited to the provided pcoord types).
The data type.
(Optional) The allocator type.

As a geometric container, it is useful to have a way to iterate through elements by axis, and for this purpose we provide hash_matrix::navigator and hash_matrix::const_navigator. They work similarly to iterators, except that it is not possible to increment and decrement them directly. Instead, they have x, y, and (for 3D) z members, which allow intuitive semantics like ++nav.x, nav.y++, --nav.z, etc. Another important difference is that navigators may be at "empty" locations: they may represent any valid coordinate, but are only dereferenceable if there is an element associated with the coordinate in the container. To determine if the navigator is dereferencable, they provide the valid() method.

Member Typedef Documentation

typedef _Alloc ash::hashmatrix::allocator_type

typedef value_type const* ash::hashmatrix::const_pointer

The type that serves as a const pointer to value_type.

Concept: stl::container

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef value_type const& ash::hashmatrix::const_reference

The type that serves as a pointer to value_type.

Concept: stl::container

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef sign<size_type>::type ash::hashmatrix::difference_type

The signed integral type used to represent the distance between iterators.

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

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

The functor type used to hash keys.

Concept: stl::hashed_associative_container

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef _KeyAccess ash::hashmatrix::key_access

Concept: ash::hashmatrix

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

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

The functor used to compare keys for equality.

Concept: stl::hashed_associative_container

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef _Morton ash::hashmatrix::key_type

The type of key associated with objects in the container.

We use this type as the key for conversion convenience. Any method that takes a key_type as an argument may take any of the following:

pcoord_type
morton_type
size_type

In the case of a pcoord_type, conversion to key_type will hash it. Otherwise it is treated as a pre-hashed key.

Concept: ash::hash_matrix

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef _Morton ash::hashmatrix::morton_type

The type used to represent a hashed/interleaved coordinate.

Conversion-compatible with pcoord_type. Conversion-compatible with size_type.

See also:: MortonXY; MortonXYZ

Concept: ash::hash_matrix

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef _Morton::pcoord_type ash::hashmatrix::pcoord_type

The type used to represent a coordinate.

Conversion-compatible with morton_type.

See also:: PCoordXY; PCoordXYZ

Concept: ash::hash_matrix

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef _ASH_POINT_T<dim_cast<_Morton::D>::D> ash::hashmatrix::point_type

The type used to represent a floating-point coordinate.

Note:: You may change this in ash_config.h.

Concept: ash::hash_matrix

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef value_type* ash::hashmatrix::pointer

The type that serves as a pointer to value_type.

Concept: stl::container

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef value_type& ash::hashmatrix::reference

The type that serves as a reference to value_type.

Concept: stl::container

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef _Morton::value_type ash::hashmatrix::size_type

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

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

typedef _Val ash::hashmatrix::value_type

The type of the object the container holds.

Must be Assignable .

Concept: stl::container

Reimplemented in ash::dense_hashmatrix< Coord, Data, Alloc >, and ash::sparse_hashmatrix< Coord, Data, Alloc >.

Constructor & Destructor Documentation

ash::hashmatrix::hashmatrix	(	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::hashmatrix::hashmatrix	(	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::hashmatrix::begin ( ) [inline]

Get an iterator to the beginning.

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

Concept: stl::container

const_iterator ash::hashmatrix::begin ( ) const [inline]

Get an iterator to the beginning.

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

Concept: stl::container

local_iterator ash::hashmatrix::begin ( size_type i ) [inline]

Concept: tr1::unordered_associative_container

const_local_iterator ash::hashmatrix::begin ( size_type i ) const [inline]

Concept: tr1::unordered_associative_container

size_type ash::hashmatrix::bucket ( key_type const & key ) const [inline]

Concept: tr1::unordered_associative_container

size_type ash::hashmatrix::bucket_count ( ) const [inline]

Get the number of buckets the container has.

Returns:: The number of currently-allocated buckets.

Concept: stl::hashed_associative_container

Todo:: Loki: This is ugly, fix this on the hashtable end.

size_type ash::hashmatrix::bucket_size ( size_type i ) const [inline]

Concept: tr1::unordered_associative_container

void ash::hashmatrix::clear ( ) [inline]

Erase all elements.

Concept: stl::associative_container

size_type ash::hashmatrix::count ( key_type const & key ) const [inline]

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

bool ash::hashmatrix::empty ( ) const [inline]

Check if the container is empty.

Returns:: True if the container is empty.

Concept: stl::container

iterator ash::hashmatrix::end ( ) [inline]

Get an iterator to the end.

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

Concept: stl::container

const_iterator ash::hashmatrix::end ( ) const [inline]

Get an iterator to the end.

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

Concept: stl::container

local_iterator ash::hashmatrix::end ( size_type i ) [inline]

Concept: tr1::unordered_associative_container

const_local_iterator ash::hashmatrix::end ( size_type i ) const [inline]

Concept: tr1::unordered_associative_container

iterator_pair ash::hashmatrix::equal_range ( key_type const & key ) [inline]

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

const_iterator_pair ash::hashmatrix::equal_range ( key_type const & key ) const [inline]

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

void ash::hashmatrix::erase ( iterator itr ) [inline]

Erase an element.

Parameters:

itr	An iterator pointing to the element to erase.

Concept: stl::associative_container

void ash::hashmatrix::erase	(	iterator	f,
		iterator	l
	)		`[inline]`

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

iterator ash::hashmatrix::find ( key_type const & key ) [inline]

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

const_iterator ash::hashmatrix::find ( key_type const & key ) const [inline]

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

hasher ash::hashmatrix::hash_funct ( ) const [inline]

Get the hash functor used by the container.

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

Concept: stl::hashed_associative_container

hasher ash::hashmatrix::hash_function ( ) const [inline]

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::hashmatrix::insert ( const_reference obj ) [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

template<class InputIterator >

void ash::hashmatrix::insert	(	InputIterator	f,
		InputIterator	l
	)		`[inline]`

Insert a range of elements [f,l) into the container.

Parameters:

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

Elements with duplicate keys will be ignored.

Concept: stl::unique_associative_container

key_equal ash::hashmatrix::key_eq ( ) const [inline]

Get the key comparison functor used by the container.

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

Concept: stl::hashed_associative_container

float ash::hashmatrix::load_factor ( ) const [inline]

Concept: tr1::unordered_associative_container

size_type ash::hashmatrix::max_bucket_count ( ) const [inline]

Concept: stl::hashed_associative_container

Todo:: Loki: This is ugly, fix this on the hashtable end.

float ash::hashmatrix::max_load_factor ( ) const [inline]

Concept: tr1::unordered_associative_container

void ash::hashmatrix::max_load_factor ( float new_grow ) [inline]

Concept: tr1::unordered_associative_container

size_type ash::hashmatrix::max_size ( ) const [inline]

Get the maximum size of the container.

Returns:: The maximum number of elements the container can hold.

Concept: stl::container

Todo:: Loki: This is ugly, fix this on the hashtable end.

float ash::hashmatrix::min_load_factor ( ) const [inline]

Get the min load factor.

Returns:: The min load factor before the container shrinks.

void ash::hashmatrix::min_load_factor ( float new_shrink ) [inline]

Set the min load factor.

Parameters:

new_shrink The min load factor before the container shrinks.

navigator ash::hashmatrix::navigate ( key_type const & key ) [inline]

Concept: ash::hash_matrix

const_navigator ash::hashmatrix::navigate ( key_type const & key ) const [inline]

Concept: ash::hash_matrix

path_iterator ash::hashmatrix::path_begin	(	point_type const &	p1,
		point_type const &	p2
	)		`[inline]`

Get an iterator from point A to point B.

Note:: There is no path_end(), use the normal end().

Parameters:

pa	Point A.
pb	Point B.

Returns:: A path_iterator pointing to the beginning of the path.

Concept: ash::hash_matrix

const_path_iterator ash::hashmatrix::path_begin	(	point_type const &	p1,
		point_type const &	p2
	)		const `[inline]`

Get an iterator from point A to point B.

Note:: There is no path_end(), use the normal end().

Parameters:

pa	Point A.
pb	Point B.

Returns:: A path_iterator pointing to the beginning of the path.

Concept: ash::hash_matrix

range_iterator ash::hashmatrix::range_begin	(	key_type const &	key,
		size_type	range
	)		`[inline]`

Hash-Matrix concept. ,range_begin(key_type const&,size_type)

,range_begin(key_type const&,size_type)

const_range_iterator ash::hashmatrix::range_begin	(	key_type const &	key,
		size_type	range
	)		const `[inline]`

Get an iterator to go through all elements in a given range.

Note:: There is no range_end(), use the normal end().

Parameters:

pos	The center of the area.
range	The max 1-dimensional distance from `pos`.

Returns:: A const_range_iterator to go through all elements within range of pos.

Concept: ash::hash_matrix

void ash::hashmatrix::rehash ( size_type n ) [inline]

Concept: tr1::unordered_associative_container

void ash::hashmatrix::resize ( size_type n ) [inline]

Resize the container to hold at least n elements.

Parameters:

n	The number of elements the container is expected to hold.

Concept: stl::hashed_associative_container

size_type ash::hashmatrix::size ( ) const [inline]

Get the size of the container.

Returns:: The number of elements in the container.

Concept: stl::container

void ash::hashmatrix::swap ( hashmatrix & obj ) [inline]

Concept: ash::hash_matrix

Member Data Documentation

const DIM ash::hashmatrix::D = dim_cast<_Morton::D>::D [static]

Concept: ash::hash_matrix

const hashmatrix< _Val, _Morton, _KeyAccess, _Alloc, _Ht >::size_type ash::hashmatrix::deleted_key = impl::matrix_keys<_Morton>::deleted_key [static]

Concept: ash::hash_matrix

const hashmatrix< _Val, _Morton, _KeyAccess, _Alloc, _Ht >::size_type ash::hashmatrix::empty_key = impl::matrix_keys<_Morton>::empty_key [static]

Concept: ash::hash_matrix

const hashmatrix< _Val, _Morton, _KeyAccess, _Alloc, _Ht >::pcoord_type ash::hashmatrix::pcoord_max [static]

Initial value:

                typename  hashmatrix<_Val,_Morton,_KeyAccess,_Alloc,_Ht> ::pcoord_type(impl::matrix_keys<_Morton>::pcoord_max)

Concept: ash::hash_matrix

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

ash/impl/hashmatrix.h
ash/impl/hashmatrix.tcc

Classes

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Protected Attributes

Related Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation