DGtal::ImageContainerByHashTree< TDomain, TValueType, 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 <ImageContainerByHashTreedav.h>

Collaboration diagram for DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >:
Collaboration graph
[legend]

Data Structures

class  Iterator
class  Node
struct  POW
struct  POW< X, 1 >

Public Types

typedef THashKey HashKey
typedef TValueType ValueType
typedef TDomain Domain
typedef Domain::Point Point
typedef Domain::Vector Vector

Public Member Functions

 ImageContainerByHashTree (unsigned hashKeySize, unsigned depth, ValueType defaultValue)
 ImageContainerByHashTree (unsigned hashKeySize, Point p1, Point p2, ValueType defaultValue)
 ImageContainerByHashTree (ImageContainerByHashTree< Domain, ValueType > &toCopy)
ValueType get (HashKey key) const
ValueType operator() (HashKey key) const
ValueType operator() (const Point &aPoint) const
ValueType get (const Point &aPoint) const
ValueType upwardGet (HashKey key) const
ValueType reverseGet (HashKey key) const
void setVal (ValueType object, HashKey key)
unsigned getSpanSize () const
unsigned getDepth () const
bool isKeyValid (HashKey key) const
bool checkIntegrity (HashKey key=ROOT_KEY, bool leafAbove=false) const
HashKey getKey (int coordinates[dim]) const
unsigned getKeyDepth (HashKey key) const
int * getCoordinatesFromKey (HashKey key) const
void save (std::ostream &out)
void load (std::istream &in)
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 nbBits=0) const
void printInfo (std::ostream &out) const
unsigned getNbEmptyLists () const
double getAverageCollisions () const
unsigned getMaxCollisions () const
unsigned getNbNodes (unsigned intermediateKey) const
unsigned getNbNodes () const
Iterator begin ()
Iterator end ()
void selfDisplay (std::ostream &out)
bool isValid () const

Data Fields

int myDebugCounter

Static Public Attributes

static const
TDomain::Space::DimensionType 
dim = TDomain::staticDimension
static const
TDomain::Space::DimensionType 
staticDimension = TDomain::staticDimension
static const unsigned int NbChildrenPerNode = POW<2,staticDimension>::VALUE
static const uint64_t ROOT_KEY = static_cast<HashKey>(1)

Protected Member Functions

HashKey getIntermediateKey (HashKey key) const
NodeaddNode (ValueType object, HashKey key)
NodegetNode (HashKey key) const
bool removeNode (HashKey key)
void recursiveRemoveNode (HashKey key, unsigned nbRecursions)
void setDepth (unsigned depth)
ValueType blendChildren (HashKey key) const

Protected Attributes

Node ** myData
unsigned myKeySize
unsigned myArraySize
unsigned myTreeDepth
unsigned mySpanSize
HashKey myDepthMask
HashKey myPreComputedIntermediateMask

Detailed Description

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
class DGtal::ImageContainerByHashTree< TDomain, TValueType, 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 obatained 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 dimmension. 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 off 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.


Member Typedef Documentation

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
typedef TDomain DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::Domain
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
typedef THashKey DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::HashKey
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
typedef Domain::Point DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::Point
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
typedef TValueType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::ValueType
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
typedef Domain::Vector DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::Vector

Constructor & Destructor Documentation

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::ImageContainerByHashTree ( unsigned  hashKeySize,
unsigned  depth,
ValueType  defaultValue 
)

The constructor.

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 the "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)
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::ImageContainerByHashTree ( unsigned  hashKeySize,
Point  p1,
Point  p2,
ValueType  defaultValue 
)
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::ImageContainerByHashTree ( ImageContainerByHashTree< Domain, ValueType > &  toCopy  ) 

Member Function Documentation

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
Node* DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::addNode ( ValueType  object,
HashKey  key 
) [inline, protected]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
Iterator DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::begin (  )  [inline]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
ValueType DGtal::ImageContainerByHashTree< TDomain, TValueType, 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.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
bool DGtal::ImageContainerByHashTree< TDomain, TValueType, 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.

Referenced by DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::isValid().

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
Iterator DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::end (  )  [inline]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
ValueType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::get ( const Point aPoint  )  const

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

Parameters:
aPoint The point.
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
ValueType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::get ( 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).

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
double DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getAverageCollisions (  )  const

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

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
int* DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getCoordinatesFromKey ( HashKey  key  )  const
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getDepth (  )  const [inline]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
HashKey DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getIntermediateKey ( HashKey  key  )  const [inline, protected]

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.

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

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
HashKey DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getKey ( int  coordinates[dim]  )  const
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getKeyDepth ( HashKey  key  )  const
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getMaxCollisions (  )  const

Returns the highest number of collisions in the hash table.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getNbEmptyLists (  )  const

Returns the number of empty places in the hash table.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getNbNodes (  )  const

Returns the total amount of elements in the container.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getNbNodes ( unsigned  intermediateKey  )  const

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

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
Node* DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getNode ( HashKey  key  )  const [inline, protected]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::getSpanSize (  )  const [inline]

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

References DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::mySpanSize.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
bool DGtal::ImageContainerByHashTree< TDomain, TValueType, 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.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
bool DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::isValid (  )  const [inline]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::load ( std::istream &  in  ) 

Load the container from a stream.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
ValueType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::operator() ( const Point aPoint  )  const

Returns the value at a given point.

Parameters:
aPoint The point.
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
ValueType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::operator() ( HashKey  key  )  const

Returns the value at a given key.

Parameters:
key the hash key used as an index.
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::printInfo ( std::ostream &  out  )  const

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

  • 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.
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::printInternalState ( std::ostream &  out,
unsigned  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.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::printState ( std::ostream &  out,
bool  displayKeys = false 
) const

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

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::printTree ( HashKey  key,
std::ostream &  out,
bool  displayKeys 
) const

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

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::recursiveRemoveNode ( HashKey  key,
unsigned  nbRecursions 
) [protected]

Recusrively calls RemoveNode on the key and its children.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
bool DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::removeNode ( HashKey  key  )  [protected]

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

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
ValueType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::reverseGet ( 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.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::save ( std::ostream &  out  ) 

Save the container into a stream.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::selfDisplay ( std::ostream &  out  ) 
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::setDepth ( unsigned  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.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
void DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::setVal ( ValueType  object,
HashKey  key 
)

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 very 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

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
ValueType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::upwardGet ( HashKey  key  )  const

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


Field Documentation

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
const TDomain::Space::DimensionType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::dim = TDomain::staticDimension [static]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::myArraySize [protected]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
Node** DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::myData [protected]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
int DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::myDebugCounter
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
HashKey DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::myDepthMask [protected]

Precoputed masks to avoid recalculating it all the time

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, 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.

template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
HashKey DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::myPreComputedIntermediateMask [protected]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::mySpanSize [protected]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
unsigned DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::myTreeDepth [protected]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
const unsigned int DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::NbChildrenPerNode = POW<2,staticDimension>::VALUE [static]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
const uint64_t DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::ROOT_KEY = static_cast<HashKey>(1) [static]
template<typename TDomain, typename TValueType, typename THashKey = unsigned int>
const TDomain::Space::DimensionType DGtal::ImageContainerByHashTree< TDomain, TValueType, THashKey >::staticDimension = TDomain::staticDimension [static]

The documentation for this class was generated from the following file:
Generated on Wed Sep 29 17:30:35 2010 for DGtal by  doxygen 1.6.3