DGtal: DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey

Model of CImageContainer implementing the association key<->Value using a hash tree. This class provides a built-in iterator. More...

#include <DGtal/images/ImageContainerByHashTree.h>

Data Structures
class	Iterator
	Built-in iterator on an HashTree. This iterator visits all node in the tree. More...

class	Node

Public Types
typedef ImageContainerByHashTree< TDomain, TValue, THashKey >	Self

typedef THashKey	HashKey

typedef TDomain	Domain

typedef Domain::Point	Point

typedef Domain::Vector	Vector

typedef Domain::Integer	Integer

typedef Domain::Size	Size

typedef Domain::Dimension	Dimension

typedef Point	Vertex

typedef POW< 2, dimension >	PowHelper

typedef TValue	Value

typedef DefaultConstImageRange< Self >	ConstRange

typedef DefaultImageRange< Self >	Range

typedef SetValueIterator< Self >	OutputIterator
	output iterator More...

Public Member Functions
	BOOST_CONCEPT_ASSERT ((concepts::CDomain< TDomain >))
	domain More...

	BOOST_STATIC_CONSTANT (Dimension, dimension=Domain::dimension)
	static constants More...

	BOOST_STATIC_CONSTANT (Dimension, dim=Domain::dimension)

	BOOST_STATIC_CONSTANT (unsigned int, NbChildrenPerNode=PowHelper::VALUE)

	BOOST_STATIC_CONSTANT (HashKey, ROOT_KEY=static_cast< THashKey >(1))

	BOOST_STATIC_ASSERT ((boost::is_same< Domain, HyperRectDomain< typename Domain::Space > >::value))
	domain should be rectangular More...

	BOOST_CONCEPT_ASSERT ((concepts::CLabel< TValue >))
	values range More...

	ImageContainerByHashTree (const unsigned int hashKeySize, const unsigned int depth, const Value defaultValue)

	ImageContainerByHashTree (const unsigned int hashKeySize, const Point &p1, const Point &p2, const Value defaultValue)

	ImageContainerByHashTree (const Domain &aDomain, const unsigned int hashKeySize=3, const Value defaultValue=NumberTraits< Value >::ZERO)

const Domain &	domain () const

ConstRange	constRange () const

Range	range ()

const Self &	container () const

Self &	container ()

const Node **&	data () const noexcept

Node **&	data () noexcept

Value	get (const HashKey key) const

Value	operator() (const HashKey key) const

Value	operator() (const Point &aPoint) const

Value	get (const Point &aPoint) const

Value	upwardGet (const HashKey key) const

Value	reverseGet (const HashKey key) const

void	setValue (const HashKey key, const Value object)

void	setValue (const Point &aPoint, const Value object)

unsigned int	getSpanSize () const

unsigned int	getDepth () const

bool	isKeyValid (HashKey key) const

bool	checkIntegrity (HashKey key=ROOT_KEY, bool leafAbove=false) const

HashKey	getKey (const Point &aPoint) const

unsigned int	getKeyDepth (HashKey key) const

int *	getCoordinatesFromKey (HashKey key) const

void	printState (std::ostream &out, bool displayKeys=false) const

void	printTree (HashKey key, std::ostream &out, bool displayKeys) const

void	printInternalState (std::ostream &out, unsigned int nbBits=0) const

void	printInfo (std::ostream &out) const

unsigned int	getNbEmptyLists () const

double	getAverageCollisions () const

unsigned int	getMaxCollisions () const

unsigned int	getNbNodes (unsigned int intermediateKey) const

unsigned int	getNbNodes () const

Iterator	begin ()

Iterator	end ()

void	selfDisplay (std::ostream &out) const

bool	isValid () const

std::string	className () const

Node *	getNode (const HashKey key) const

Data Fields
int	myDebugCounter

Point	myOrigin

Morton< HashKey, Point >	myMorton
	The morton code computer. More...

Protected Member Functions
template<typename C >
void	recursiveDraw (HashKey key, const double p1[2], const double len, Board2D &board, const C &cmap) const

HashKey	getIntermediateKey (const HashKey key) const

Node *	addNode (const Value object, const HashKey key)

bool	removeNode (HashKey key)

void	recursiveRemoveNode (HashKey key, unsigned int nbRecursions)

void	setDepth (unsigned int depth)

Value	blendChildren (HashKey key) const

	BOOST_STATIC_CONSTANT (unsigned int, myN=NbChildrenPerNode)

Protected Attributes
Domain	myDomain

Node **	myData

unsigned int	myKeySize

unsigned int	myArraySize

unsigned int	myTreeDepth

unsigned int	mySpanSize

HashKey	myDepthMask

HashKey	myPreComputedIntermediateMask

Detailed Description

template<typename TDomain, typename TValue, typename THashKey = typename DGtal::uint64_t>
class DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >

Model of CImageContainer implementing the association key<->Value using a hash tree. This class provides a built-in iterator.

Description of template class 'ImageContainerByHashTree'

Todo:: doc here

The ImageContainerByHashTree relies on a tree model implemented using a hash table based on Morton Codes. A Morton hash key is obtained from coordinates by interleaving the binary representations of the coordinate values. This means the coordinates have to be of integer type for the morton code to be valid.

The data can be accessed using keys, coordinates or Iterators provided by the container.

The parent of a given key can be found by simply shifting to the left the key's bits by it's dimension. exemples: for an octree (N = 3) the parent key of the key 1110100001 is 1110100. for a quadtree (N = 2) the parent key of the key 10010111 is 100101.

It is then easy to determine, for a N-Dimmensionnal container, all the children keys of a given key, by concatenating any combination of N bits at the right side of the key (least important bits). exemple: for a quadtree (N = 2) 1010100, 1010101, 1010110 and 1010111 are the children of 10101.

In order to disgard any ambiguous case, we need to make the assertion that the root of the hash is at key 1. Else we would have to deal with the problem of the key 00000..0 which would have one of it's children equal to 0 and so on... This means that we need to set the key's N*maxDepth bit to 1 after interleaving the corrdinates bit for key generation.

Note that not any combination of bits is valid. We saw the exemple of the key 0, and there are other cases of invalidity. For a key to be valid, the last set bit (most important set bit) must be at a position of the form k*N with N the Dimmension of the Domain and k a positive integer. exemples: for an octree(N = 3) 1, 1000, 1010111 are valid keys, whereas 0, 10, 11101 are not !

Warning ! For performances this container's access method never check for a key's validity. Trying to access an invalid key may destroy the validity of the tree's structure and/or get the program stuck into an infinite loop.

The method isKeyValid(..) is provided to verify the validity of a key. Note that using this security strongly affects performances.

Template Parameters

TDomain	type of domains
TValue	type for image values
THashKey	type to store Morton keys (default: DGtal::uint64_t)

See also: testImageContainerByHashTree.cpp

Definition at line 128 of file ImageContainerByHashTree.h.

Member Typedef Documentation

◆ ConstRange

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef DefaultConstImageRange<Self> DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::ConstRange

Definition at line 167 of file ImageContainerByHashTree.h.

◆ Dimension

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef Domain::Dimension DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Dimension

Definition at line 148 of file ImageContainerByHashTree.h.

◆ Domain

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef TDomain DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Domain

Definition at line 143 of file ImageContainerByHashTree.h.

◆ HashKey

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef THashKey DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::HashKey

Definition at line 139 of file ImageContainerByHashTree.h.

◆ Integer

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef Domain::Integer DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Integer

Definition at line 146 of file ImageContainerByHashTree.h.

◆ OutputIterator

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef SetValueIterator<Self> DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::OutputIterator

output iterator

Definition at line 171 of file ImageContainerByHashTree.h.

◆ Point

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef Domain::Point DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Point

Definition at line 144 of file ImageContainerByHashTree.h.

◆ PowHelper

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef POW<2, dimension> DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::PowHelper

Definition at line 154 of file ImageContainerByHashTree.h.

◆ Range

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef DefaultImageRange<Self> DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Range

Definition at line 168 of file ImageContainerByHashTree.h.

◆ Self

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef ImageContainerByHashTree<TDomain, TValue, THashKey> DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Self

Definition at line 137 of file ImageContainerByHashTree.h.

◆ Size

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef Domain::Size DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Size

Definition at line 147 of file ImageContainerByHashTree.h.

◆ Value

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef TValue DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Value

Definition at line 165 of file ImageContainerByHashTree.h.

◆ Vector

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef Domain::Vector DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Vector

Definition at line 145 of file ImageContainerByHashTree.h.

◆ Vertex

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

typedef Point DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Vertex

Definition at line 149 of file ImageContainerByHashTree.h.

Constructor & Destructor Documentation

◆ ImageContainerByHashTree() [1/3]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::ImageContainerByHashTree	(	const unsigned int	hashKeySize,
		const unsigned int	depth,
		const Value	defaultValue
	)

The constructor from a hashKeySize, a depth and a defaultValue.

Parameters

hashKeySize	Number of bit of the hash key. This parameter is important as it influences the amount of collisions in the hash table. A value K creates an array of length 2^K with potential unused cells so a compromise between speed and memory usage is to be done here.
depth	Determines the maximum depth of the tree and thus qthe "size" of the image. Each span then extends from 0 to 2^depth.
defaultValue	In order for the tree to be valid it needs a default value at the root (key = 1)

◆ ImageContainerByHashTree() [2/3]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::ImageContainerByHashTree	(	const unsigned int	hashKeySize,
		const Point &	p1,
		const Point &	p2,
		const Value	defaultValue
	)

The constructor from a hashKeySize, a defaultValue and a pair of points. In this case, the depth of the tree is given by the logarithm of the domain size defined by the two points.

Parameters

hashKeySize	Number of bit of the hash key. This parameter is important as it influences the amount of collisions in the hash table. A value K creates an array of length 2^K with potential unused cells so a compromise between speed and memory usage is to be done here.
p1	First point of the image bounding box.
p2	Second point of the image bounding box.
defaultValue	In order for the tree to be valid it needs a default value at the root (key = 1)

◆ ImageContainerByHashTree() [3/3]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::ImageContainerByHashTree	(	const Domain &	aDomain,
		const unsigned int	hashKeySize = `3`,
		const Value	defaultValue = `NumberTraits< Value >::ZERO`
	)

The constructor from a domain, a defaultValue (default value: 0) and a hashKeySize (default value: 3). In this case, the depth of the tree is given by the logarithm of the domain size defined by the two points.

Parameters

aDomain	the image domain
hashKeySize	Number of bit of the hash key. This parameter is important as it influences the amount of collisions in the hash table. A value K creates an array of length 2^K with potential unused cells so a compromise between speed and memory usage is to be done here (default: 3).
defaultValue	In order for the tree to be valid it needs a default value at the root (key = 1)

Member Function Documentation

◆ addNode()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Node* DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::addNode	(	const Value	object,
		const HashKey	key
	)

inlineprotected

Add a Node to the tree. This method is very used when writing in the tree (set method). As detailed in the inner class Node, nodes are pairs (value,key)

Parameters

object	a object (value)
key	a hashtree key

Returns: a pointer to the node list.

Definition at line 700 of file ImageContainerByHashTree.h.

     {
       Node* n = getNode(key);
       if (n)
         {
           n->getObject() = object;
           //n->setObject(object);
           return n;
         }
       n = new Node(object, key);
       HashKey key2 = getIntermediateKey(key);
       n->setNext(myData[key2]);
       myData[key2] = n;
       return n;
     }

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getIntermediateKey(), DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getNode(), and DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myData.

◆ begin()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Iterator DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::begin ( )

inline

Returns an iterator to the first value as stored in the container.

Definition at line 571 of file ImageContainerByHashTree.h.

     {
       return Iterator(myData, 0, myArraySize);
     }

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myArraySize, and DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myData.

◆ blendChildren()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Value DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::blendChildren ( HashKey key ) const

protected

Recursively get the value of all the leafs below and blend it to get the value of a parent node. This is called in the get() method when it has been determined that the leafs are deeper than the requested key.

◆ BOOST_CONCEPT_ASSERT() [1/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::BOOST_CONCEPT_ASSERT ( (concepts::CDomain< TDomain >) )

domain

◆ BOOST_CONCEPT_ASSERT() [2/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::BOOST_CONCEPT_ASSERT ( (concepts::CLabel< TValue >) )

values range

◆ BOOST_STATIC_ASSERT()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::BOOST_STATIC_ASSERT ( (boost::is_same< Domain, HyperRectDomain< typename Domain::Space > >::value) )

domain should be rectangular

◆ BOOST_STATIC_CONSTANT() [1/5]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::BOOST_STATIC_CONSTANT	(	Dimension	,
		dim	= `Domain::dimension`
	)

◆ BOOST_STATIC_CONSTANT() [2/5]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::BOOST_STATIC_CONSTANT	(	Dimension	,
		dimension	= `Domain::dimension`
	)

static constants

◆ BOOST_STATIC_CONSTANT() [3/5]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::BOOST_STATIC_CONSTANT	(	HashKey	,
		ROOT_KEY	= `static_cast< THashKey >(1)`
	)

◆ BOOST_STATIC_CONSTANT() [4/5]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::BOOST_STATIC_CONSTANT	(	unsigned int	,
		myN	= `NbChildrenPerNode`
	)

protected

◆ BOOST_STATIC_CONSTANT() [5/5]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::BOOST_STATIC_CONSTANT	(	unsigned int	,
		NbChildrenPerNode	= `PowHelper::VALUE`
	)

◆ checkIntegrity()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

bool DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::checkIntegrity	(	HashKey	key = `ROOT_KEY`,
		bool	leafAbove = `false`
	)		const

Checks recursively that the sub-tree starting with key is valid. A tree is valid if there's one (and only one) leaf for each position at maximal depth.

Parameters

key	the key
leafAbove	leafAbove (

Todo:: )

Referenced by DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::isValid(), and test_setVal().

◆ className()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

std::string DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::className ( ) const

Default drawing style object.

Returns: the dyn. alloc. default style for this object.; the style name used for drawing this object.

◆ constRange()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

ConstRange DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::constRange ( ) const

Returns: an instance of ConstRange used to iterate over the values.

◆ container() [1/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Self& DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::container ( )

inline

Give access to the underlying container.

Returns: a (might be const) reference to the container.

Definition at line 288 of file ImageContainerByHashTree.h.

288 { return *this; };

◆ container() [2/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

const Self& DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::container ( ) const

inline

Give access to the underlying container.

Returns: a (might be const) reference to the container.

Definition at line 283 of file ImageContainerByHashTree.h.

283 { return *this; };

◆ data() [1/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

const Node** & DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::data ( ) const

inlinenoexcept

Give access to the underlying data.

Returns: a (might be const) reference to the data.

Definition at line 294 of file ImageContainerByHashTree.h.

294 { return myData; };

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myData.

Referenced by DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Iterator::Iterator().

◆ data() [2/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Node** & DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::data ( )

inlinenoexcept

Give access to the underlying data.

Returns: a (might be const) reference to the data.

Definition at line 299 of file ImageContainerByHashTree.h.

299 { return myData; };

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myData.

◆ domain()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

const Domain& DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::domain ( ) const

Returns: the domain associated to the image.

◆ end()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Iterator DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::end ( )

inline

Returns an iterator to the last value as stored in the container.

Definition at line 579 of file ImageContainerByHashTree.h.

     {
       return Iterator(myData, myArraySize, myArraySize);
     }

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myArraySize, and DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myData.

◆ get() [1/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Value DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::get ( const HashKey key ) const

Returns the value corresponding to a key.

This is the generic method working with any valid key. For efficiency no check is performed on the key so be careful when calling this method. If the leafs are deeper than the requested key, this method will recursively browse through the children nodes and compute a average of each child's value using blendChildren(..) which is very slow. Thus performances are much better when accessing a leaf from a deeper key (needs no blending).

Parameters

key	the haskkey

Returns: the value

Referenced by main(), and test_get().

◆ get() [2/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Value DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::get ( const Point & aPoint ) const

Returns the value at a given coordinate using upwardGet().

Parameters

aPoint The point

Returns: the value

◆ getAverageCollisions()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

double DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getAverageCollisions ( ) const

Returns The average number of collisions in the hash table, without counting the empty places.

◆ getCoordinatesFromKey()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

int* DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getCoordinatesFromKey ( HashKey key ) const

◆ getDepth()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getDepth ( ) const

inline

Returns the tree's depth.

Returns: the depth

Definition at line 400 of file ImageContainerByHashTree.h.

     {
       return myTreeDepth;
     }

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myTreeDepth.

◆ getIntermediateKey()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

HashKey DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getIntermediateKey ( const HashKey key ) const

inlineprotected

This is part of the hash function. It is called whenever a key is accessed. The mask used to compute the result is precomputed in the constructor for efficiency.

Parameters

key	a node in the hashtree.

Referenced by DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::addNode(), and DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getNode().

◆ getKey()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

HashKey DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getKey ( const Point & aPoint ) const

◆ getKeyDepth()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getKeyDepth ( HashKey key ) const

◆ getMaxCollisions()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getMaxCollisions ( ) const

Returns the highest number of collisions in the hash table.

◆ getNbEmptyLists()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getNbEmptyLists ( ) const

Returns the number of empty places in the hash table.

◆ getNbNodes() [1/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getNbNodes ( ) const

Returns the total amount of elements in the container.

◆ getNbNodes() [2/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getNbNodes ( unsigned int intermediateKey ) const

Returns the number of elements for a given key of the hash table.

Parameters

intermediateKey a hashtree key.

◆ getNode()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Node* DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getNode ( const HashKey key ) const

inline

Returns a pointer to the node corresponding to the key. If it does'nt exist, returns 0. This method is called VERY often, and thus should operate as fast as possible.

Parameters

key The key.

Returns: the pointer to the node corresponding to the key.

Definition at line 724 of file ImageContainerByHashTree.h.

     {
       Node* iter = myData[getIntermediateKey(key)];
       while (iter != 0)
         {
           if (iter->getKey() == key)
             return iter;
           iter = iter->getNext();
         }
       return 0;
     }

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getIntermediateKey(), DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Node::getKey(), DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::Node::getNext(), and DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myData.

Referenced by DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::addNode().

◆ getSpanSize()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getSpanSize ( ) const

inline

Returns the size of a dimension (the container represents a line, a square, a cube, etc. depending on the dimmension so no need for distinctions between width, height, ect.)

Returns: the dimension size

Definition at line 391 of file ImageContainerByHashTree.h.

     {
       return mySpanSize;
     }

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::mySpanSize.

◆ isKeyValid()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

bool DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::isKeyValid ( HashKey key ) const

Returns true if the key is valid. A key is valid if the the most important bit that is equal to 1 is at a position of the type dim*k with dim the dimmension of the container (template parameter) and k a strictly positive integer.

Parameters

key the key

Returns: the boolean result

Referenced by test_get(), and test_setVal().

◆ isValid()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

bool DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::isValid ( ) const

inline

Definition at line 586 of file ImageContainerByHashTree.h.

     {
       return checkIntegrity();
     }

References DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::checkIntegrity().

◆ operator()() [1/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Value DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::operator() ( const HashKey key ) const

Returns the value at a given key.

Parameters

key	the hash key used as an index.

Returns: the value

◆ operator()() [2/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Value DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::operator() ( const Point & aPoint ) const

Returns the value at a given point.

Parameters

aPoint The point

Returns: the value

◆ printInfo()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::printInfo ( std::ostream & out ) const

Prints informations about the state of the container without displaying the data:

- Nunber of elements in the tree.
- Amount of unused disk space due to blanks in the hash table.
- The dimmension.
- The number of bits of the HashKey.
- The size of the image.
- The average and the maximum amount of collisions.
- The total memory usage.

Parameters

out	output stream.

◆ printInternalState()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::printInternalState	(	std::ostream &	out,
		unsigned int	nbBits = `0`
	)		const

Prints the state of the container in a way that displays the hash table and every node as it is stored in memory instead of the usual tree representation.

Parameters

out	output stream.
nbBits	number of bits

◆ printState()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::printState	(	std::ostream &	out,
		bool	displayKeys = `false`
	)		const

Prints in the state of the container as a tree. (Calls printTree)

Parameters

out	output stream.
displayKeys	boolean to decide if keys are displayed .

◆ printTree()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::printTree	(	HashKey	key,
		std::ostream &	out,
		bool	displayKeys
	)		const

Prints the sub-tree starting with the node corresponding to key.

Parameters

key	root of the subtree to display
out	output stream.
displayKeys	boolean to decide if keys are displayed .

◆ range()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Range DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::range ( )

Returns: an instance of ConstRange used to iterate over the values.

◆ recursiveDraw()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

template<typename C >

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::recursiveDraw	(	HashKey	key,
		const double	p1[2],
		const double	len,
		Board2D &	board,
		const C &	cmap
	)		const

protected

◆ recursiveRemoveNode()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::recursiveRemoveNode	(	HashKey	key,
		unsigned int	nbRecursions
	)

protected

Recusrively calls RemoveNode on the key and its children.

Parameters

key	The key.
nbRecursions	the number of recursions performed.

◆ removeNode()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

bool DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::removeNode ( HashKey key )

protected

Remove the node corresponding to a key. Returns false if the node doesn't exist.

Parameters

key The key

◆ reverseGet()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Value DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::reverseGet ( const HashKey key ) const

A attempt to do the same thing as get(HashKey) but looking for deeper leafs in the first place instead of doing this in the second place. It hasn't show better results so far.

Parameters

key The key.

Returns: the value

◆ selfDisplay()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::selfDisplay ( std::ostream & out ) const

◆ setDepth()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::setDepth ( unsigned int depth )

protected

Set the (maximum) depth of the tree and precompute a mask used for some calculations. The depth of the tree must be known because accessing the data from coordinates depends on it.

Parameters

depth the maxumum depth.

◆ setValue() [1/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::setValue	(	const HashKey	key,
		const Value	object
	)

Sets the value of an element in the container, creating it if necessary. In order to keep the tree's coherence this method may add and remove several other nodes in the tree so performances strongly depend on wether or not and how much the tree's structure needs to be modified. For efficiency no check is performed on the key

Parameters

key	The key
object	The associated object

Referenced by test_get(), and test_setVal().

◆ setValue() [2/2]

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

void DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::setValue	(	const Point &	aPoint,
		const Value	object
	)

Parameters

aPoint	The point
object	the associated object

◆ upwardGet()

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Value DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::upwardGet ( const HashKey key ) const

Returns the value corresponding to a key making the assumption that the key is at same depth or deeper than the leaf we are looking for.

Parameters

key The key.

Returns: the value.

Field Documentation

◆ myArraySize

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myArraySize

protected

Definition at line 789 of file ImageContainerByHashTree.h.

Referenced by DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::begin(), and DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::end().

◆ myData

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Node** DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myData

protected

The array of linked lists containing all the data

Definition at line 780 of file ImageContainerByHashTree.h.

Referenced by DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::addNode(), DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::begin(), DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::data(), DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::end(), and DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getNode().

◆ myDebugCounter

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myDebugCounter

Definition at line 424 of file ImageContainerByHashTree.h.

◆ myDepthMask

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

HashKey DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myDepthMask

protected

Precoputed masks to avoid recalculating it all the time

Definition at line 810 of file ImageContainerByHashTree.h.

◆ myDomain

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Domain DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myDomain

protected

The image domain

Definition at line 775 of file ImageContainerByHashTree.h.

◆ myKeySize

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myKeySize

protected

The size of the intermediate hashkey. The bigger the less collisions, but at the same time the more chances to have unused memory allocated.

Definition at line 787 of file ImageContainerByHashTree.h.

◆ myMorton

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Morton<HashKey, Point> DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myMorton

The morton code computer.

Definition at line 815 of file ImageContainerByHashTree.h.

◆ myOrigin

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

Point DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myOrigin

Definition at line 804 of file ImageContainerByHashTree.h.

◆ myPreComputedIntermediateMask

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

HashKey DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myPreComputedIntermediateMask

protected

Definition at line 811 of file ImageContainerByHashTree.h.

◆ mySpanSize

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::mySpanSize

protected

Definition at line 796 of file ImageContainerByHashTree.h.

Referenced by DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getSpanSize().

◆ myTreeDepth

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>

unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myTreeDepth

protected

The depth of the tree

Definition at line 794 of file ImageContainerByHashTree.h.

Referenced by DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::getDepth().

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

ImageContainerByHashTree.h

Data Structures

Public Types

Public Member Functions

Data Fields

Protected Member Functions

Protected Attributes

Detailed Description

template<typename TDomain, typename TValue, typename THashKey = typename DGtal::uint64_t> class DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >

Member Typedef Documentation

◆ ConstRange

◆ Dimension

◆ Domain

◆ HashKey

◆ Integer

◆ OutputIterator

◆ Point

◆ PowHelper

◆ Range

◆ Self

◆ Size

◆ Value

◆ Vector

◆ Vertex

Constructor & Destructor Documentation

◆ ImageContainerByHashTree() [1/3]

◆ ImageContainerByHashTree() [2/3]

◆ ImageContainerByHashTree() [3/3]

Member Function Documentation

◆ addNode()

◆ begin()

◆ blendChildren()

◆ BOOST_CONCEPT_ASSERT() [1/2]

◆ BOOST_CONCEPT_ASSERT() [2/2]

◆ BOOST_STATIC_ASSERT()

◆ BOOST_STATIC_CONSTANT() [1/5]

◆ BOOST_STATIC_CONSTANT() [2/5]

◆ BOOST_STATIC_CONSTANT() [3/5]

◆ BOOST_STATIC_CONSTANT() [4/5]

◆ BOOST_STATIC_CONSTANT() [5/5]

◆ checkIntegrity()

◆ className()

◆ constRange()

◆ container() [1/2]

◆ container() [2/2]

◆ data() [1/2]

◆ data() [2/2]

◆ domain()

◆ end()

◆ get() [1/2]

◆ get() [2/2]

◆ getAverageCollisions()

◆ getCoordinatesFromKey()

◆ getDepth()

◆ getIntermediateKey()

◆ getKey()

◆ getKeyDepth()

◆ getMaxCollisions()

◆ getNbEmptyLists()

◆ getNbNodes() [1/2]

◆ getNbNodes() [2/2]

◆ getNode()

◆ getSpanSize()

◆ isKeyValid()

◆ isValid()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ printInfo()

◆ printInternalState()

◆ printState()

◆ printTree()

◆ range()

◆ recursiveDraw()

◆ recursiveRemoveNode()

◆ removeNode()

◆ reverseGet()

◆ selfDisplay()

◆ setDepth()

◆ setValue() [1/2]

◆ setValue() [2/2]

◆ upwardGet()

template<typename TDomain, typename TValue, typename THashKey = typename DGtal::uint64_t>
class DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >