Public Types | Static Public Attributes | Protected Types | Protected Attributes | Related Functions
ash::sparse_hashmatrix< Coord, Data, Alloc > Class Template Reference

A hashmatrix with sparse_hashtable as a backend. More...

#include <ash/sparse_hashmatrix.h>

Inheritance diagram for ash::sparse_hashmatrix< Coord, Data, Alloc >:
Inheritance graph
[legend]

List of all members.

Public Types

typedef Coord::morton_type key_type
 The type of key associated with objects in the container.
typedef Data data_type
typedef pair< const key_type,
Data > 
value_type
 The type of the object the container holds.
typedef value_typepointer
 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_typereference
 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 _Base::size_type size_type
 The unsigned type used to represent the size of the container.
typedef _Base::difference_type difference_type
 The signed integral type used to represent the distance between iterators.
typedef _Base::morton_type morton_type
 The type used to represent a hashed/interleaved coordinate.
typedef _Base::pcoord_type pcoord_type
 The type used to represent a coordinate.
typedef _Base::point_type point_type
 The type used to represent a floating-point coordinate.
typedef _Base::hasher hasher
 The functor type used to hash keys.
typedef _Base::iterator iterator
typedef _Base::const_iterator const_iterator
typedef _Base::navigator navigator
typedef _Base::const_navigator const_navigator
typedef _Base::range_iterator range_iterator
typedef _Base::const_range_iterator const_range_iterator
typedef _Base::path_iterator path_iterator
typedef _Base::const_path_iterator const_path_iterator
typedef _Base::key_equal key_equal
 The functor used to compare keys for equality.
typedef _Base::key_access key_access
 
typedef _Alloc allocator_type
 

Public Member Functions

Constructors/Destructors

We use the default copy constructor.

We use the default destructor.

 sparse_hashmatrix (size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
 Default constructor.
template<class InputIterator >
 sparse_hashmatrix (InputIterator const &f, InputIterator const &l, size_type n=0, hasher const &h=hasher(), key_equal const &k=key_equal())
 Iterative constructor.
Lookup Methods
data_type & operator[] (key_type const &key)
 Element access.
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.

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 _Type dense_hashmatrix_type
typedef _Base hashmatrix_type
typedef _Base::hashtable_type hashtable_type
typedef table_value_allocator
< typename _Alloc::template
rebind< _Val >::other > 
hashtable_allocator
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, iteratoriterator_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

template<class Coord, typename Data, class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
class ash::sparse_hashmatrix< Coord, Data, Alloc >

A hashmatrix with sparse_hashtable as a backend.

Concepts:
ash::hash_matrix
Concepts:
stl::unique_hashed_associative_container
Concepts:
stl::pair_associative_container
Template Parameters:
Coord[PCoordXY<>|PCoordXYZ<>] The coordinate type.
DataThe data type associated with a Key. Also defined as sparse_hashmatrix::data_type.
AllocThe allocator type - passed to the base class for implementation.

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:

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 [inherited]

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef value_type const* ash::sparse_hashmatrix< Coord, Data, Alloc >::const_pointer

The type that serves as a const pointer to value_type.



Concept: stl::container

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef value_type const& ash::sparse_hashmatrix< Coord, Data, Alloc >::const_reference

The type that serves as a pointer to value_type.



Concept: stl::container

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef _Base::difference_type ash::sparse_hashmatrix< Coord, Data, Alloc >::difference_type

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

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef _Base::hasher ash::sparse_hashmatrix< Coord, Data, Alloc >::hasher

The functor type used to hash keys.



Concept: stl::hashed_associative_container

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef _Base::key_access ash::sparse_hashmatrix< Coord, Data, Alloc >::key_access



Concept: ash::hashmatrix

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef _Base::key_equal ash::sparse_hashmatrix< Coord, Data, Alloc >::key_equal

The functor used to compare keys for equality.



Concept: stl::hashed_associative_container

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef Coord::morton_type ash::sparse_hashmatrix< Coord, Data, Alloc >::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 from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef _Base::morton_type ash::sparse_hashmatrix< Coord, Data, Alloc >::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 from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef _Base::pcoord_type ash::sparse_hashmatrix< Coord, Data, Alloc >::pcoord_type

The type used to represent a coordinate.

Conversion-compatible with morton_type.

See also:
PCoordXY
PCoordXYZ


Concept: ash::hash_matrix

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef _Base::point_type ash::sparse_hashmatrix< Coord, Data, Alloc >::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 from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef value_type* ash::sparse_hashmatrix< Coord, Data, Alloc >::pointer

The type that serves as a pointer to value_type.



Concept: stl::container

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef value_type& ash::sparse_hashmatrix< Coord, Data, Alloc >::reference

The type that serves as a reference to value_type.



Concept: stl::container

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef _Base::size_type ash::sparse_hashmatrix< Coord, Data, Alloc >::size_type

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

Reimplemented from ash::hashmatrix.

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
typedef pair<const key_type, Data> ash::sparse_hashmatrix< Coord, Data, Alloc >::value_type

The type of the object the container holds.

Must be Assignable .

Concept: stl::container

Reimplemented from ash::hashmatrix.


Constructor & Destructor Documentation

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
ash::sparse_hashmatrix< Coord, Data, Alloc >::sparse_hashmatrix ( size_type  n = 0,
hasher const &  h = hasher(),
key_equal const &  k = key_equal() 
) [inline, explicit]

Default constructor.

Parameters:
nThe number of expected elements.
hThe hasher object to copy, if any.
kThe key_equal object to copy, if any.
template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
template<class InputIterator >
ash::sparse_hashmatrix< Coord, Data, Alloc >::sparse_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:
fThe beginning of the range of elements to insert.
lThe end of the range of elements to insert.
nThe number of expected elements.
hThe hasher object to copy, if any.
kThe key_equal object to copy, if any.

Member Function Documentation

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

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, inherited]

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, inherited]
const_local_iterator ash::hashmatrix::begin ( size_type  i) const [inline, inherited]
size_type ash::hashmatrix::bucket ( key_type const &  key) const [inline, inherited]
size_type ash::hashmatrix::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

Todo:
Loki: This is ugly, fix this on the hashtable end.
size_type ash::hashmatrix::bucket_size ( size_type  i) const [inline, inherited]
void ash::hashmatrix::clear ( ) [inline, inherited]

Erase all elements.



Concept: stl::associative_container

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

Count the number of elements with a given key.

Parameters:
keyThe 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, inherited]

Check if the container is empty.

Returns:
True if the container is empty.


Concept: stl::container

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

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, inherited]

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, inherited]
const_local_iterator ash::hashmatrix::end ( size_type  i) const [inline, inherited]
iterator_pair ash::hashmatrix::equal_range ( key_type const &  key) [inline, inherited]

Find all elements matching a given key.

Parameters:
keyThe 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, inherited]

Find all elements matching a given key.

Parameters:
keyThe 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, inherited]

Erase an element.

Parameters:
itrAn iterator pointing to the element to erase.


Concept: stl::associative_container

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

Erase a range of elements.

Parameters:
fThe beginning of the range to erase.
lThe end of the range to erase.


Concept: stl::associative_container

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

Find an element.

Parameters:
keyThe 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, inherited]

Find an element.

Parameters:
keyThe 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, 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::hashmatrix::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::hashmatrix::insert ( const_reference  obj) [inline, inherited]

Insert an element into the container.

Parameters:
objThe 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, inherited]

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

Parameters:
fThe beginning of the range to insert.
lThe 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, inherited]

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, inherited]
size_type ash::hashmatrix::max_bucket_count ( ) const [inline, inherited]



Concept: stl::hashed_associative_container

Todo:
Loki: This is ugly, fix this on the hashtable end.
float ash::hashmatrix::max_load_factor ( ) const [inline, inherited]
void ash::hashmatrix::max_load_factor ( float  new_grow) [inline, inherited]
size_type ash::hashmatrix::max_size ( ) const [inline, inherited]

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, inherited]

Get the min load factor.

Returns:
The min load factor before the container shrinks.
void ash::hashmatrix::min_load_factor ( float  new_shrink) [inline, inherited]

Set the min load factor.

Parameters:
new_shrinkThe min load factor before the container shrinks.
navigator ash::hashmatrix::navigate ( key_type const &  key) [inline, inherited]



Concept: ash::hash_matrix

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



Concept: ash::hash_matrix

template<class Coord , typename Data , class Alloc = libc_allocator_with_realloc< pair<const typename Coord::morton_type, Data> >>
data_type& ash::sparse_hashmatrix< Coord, Data, Alloc >::operator[] ( key_type const &  key) [inline]

Element access.

Parameters:
keyThe key of the element to access.
Returns:
A reference to the corresponding data value. If an element with the key does not exist, it will be inserted.
path_iterator ash::hashmatrix::path_begin ( point_type const &  p1,
point_type const &  p2 
) [inline, inherited]

Get an iterator from point A to point B.

Note:
There is no path_end(), use the normal end().
Parameters:
paPoint A.
pbPoint 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, inherited]

Get an iterator from point A to point B.

Note:
There is no path_end(), use the normal end().
Parameters:
paPoint A.
pbPoint 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, inherited]
const_range_iterator ash::hashmatrix::range_begin ( key_type const &  key,
size_type  range 
) const [inline, inherited]

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

Note:
There is no range_end(), use the normal end().
Parameters:
posThe center of the area.
rangeThe 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, inherited]
void ash::hashmatrix::resize ( size_type  n) [inline, inherited]

Resize the container to hold at least n elements.

Parameters:
nThe number of elements the container is expected to hold.


Concept: stl::hashed_associative_container

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

Get the size of the container.

Returns:
The number of elements in the container.


Concept: stl::container

void ash::hashmatrix::swap ( hashmatrix obj) [inline, inherited]



Concept: ash::hash_matrix


Member Data Documentation

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



Concept: ash::hash_matrix

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



Concept: ash::hash_matrix

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



Concept: ash::hash_matrix

const hashmatrix< _Val, _Morton, _KeyAccess, _Alloc, _Ht >::pcoord_type ash::hashmatrix::pcoord_max [static, inherited]
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 file:


© 2012   AshTL
Licensed under  AGPLv3
Hosted by  Get AshTL at SourceForge.net. Fast, secure and Free Open Source software downloads
Generated by  doxygen 1.7.4