DGtal  1.4.beta
DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey > Class Template Reference

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< SelfConstRange
 
typedef DefaultImageRange< SelfRange
 
typedef SetValueIterator< SelfOutputIterator
 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 Domaindomain () const
 
ConstRange constRange () const
 
Range range ()
 
const Selfcontainer () const
 
Selfcontainer ()
 
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
 
NodegetNode (const HashKey key) const
 

Data Fields

int myDebugCounter
 
Point myOrigin
 
Morton< HashKey, PointmyMorton
 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
 
NodeaddNode (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
TDomaintype of domains
TValuetype for image values
THashKeytype 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
hashKeySizeNumber 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.
depthDetermines the maximum depth of the tree and thus qthe "size" of the image. Each span then extends from 0 to 2^depth.
defaultValueIn 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
hashKeySizeNumber 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.
p1First point of the image bounding box.
p2Second point of the image bounding box.
defaultValueIn 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 = NumberTraitsValue >::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
aDomainthe image domain
hashKeySizeNumber 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).
defaultValueIn 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
objecta object (value)
keya hashtree key
Returns
a pointer to the node list.

Definition at line 700 of file ImageContainerByHashTree.h.

701  {
702  Node* n = getNode(key);
703  if (n)
704  {
705  n->getObject() = object;
706  //n->setObject(object);
707  return n;
708  }
709  n = new Node(object, key);
710  HashKey key2 = getIntermediateKey(key);
711  n->setNext(myData[key2]);
712  myData[key2] = n;
713  return n;
714  }
HashKey getIntermediateKey(const HashKey key) const

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

◆ 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
keythe key
leafAboveleafAbove (
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.

580  {
581  return Iterator(myData, myArraySize, myArraySize);
582  }

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
keythe 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
aPointThe 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.

401  {
402  return myTreeDepth;
403  }

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
keya 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
intermediateKeya 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
keyThe key.
Returns
the pointer to the node corresponding to the key.

Definition at line 724 of file ImageContainerByHashTree.h.

725  {
726  Node* iter = myData[getIntermediateKey(key)];
727  while (iter != 0)
728  {
729  if (iter->getKey() == key)
730  return iter;
731  iter = iter->getNext();
732  }
733  return 0;
734  }

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.

392  {
393  return mySpanSize;
394  }

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
keythe 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.

587  {
588  return checkIntegrity();
589  }
bool checkIntegrity(HashKey key=ROOT_KEY, bool leafAbove=false) const

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
keythe 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
aPointThe 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
outoutput 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
outoutput stream.
nbBitsnumber 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
outoutput stream.
displayKeysboolean 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
keyroot of the subtree to display
outoutput stream.
displayKeysboolean 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
keyThe key.
nbRecursionsthe 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
keyThe 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
keyThe 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
depththe 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
keyThe key
objectThe 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 
)

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 coordinates

Parameters
aPointThe point
objectthe 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
keyThe 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

◆ myData

◆ 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

◆ myTreeDepth

template<typename TDomain , typename TValue , typename THashKey = typename DGtal::uint64_t>
unsigned int DGtal::experimental::ImageContainerByHashTree< TDomain, TValue, THashKey >::myTreeDepth
protected

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