DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey > Class Template Reference

#include <ImageContainerByHashTree.h>

Collaboration diagram for DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >:

Data Structures
class	Iterator
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 TValue	Value
typedef ConstRangeAdapter < typename Domain::ConstIterator, Self, Value >	ConstRange
typedef SetValueIterator< Self >	OutputIterator

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CDomain< TDomain >))
	BOOST_STATIC_ASSERT ((boost::is_same< Domain, HyperRectDomain< SpaceND< dimension, Integer > > >::value))
	BOOST_CONCEPT_ASSERT ((CLabel< TValue >))
	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	range () const
OutputIterator	outputIterator ()
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)
bool	isValid () const
std::string	className () const
Node *	getNode (const HashKey key) const

Data Fields
int	myDebugCounter
Point	myOrigin
Morton< HashKey, Point >	myMorton

Static Public Attributes
static const Domain::Dimension	dimension = Domain::dimension
static const Domain::Dimension	dim = Domain::dimension
static const unsigned int	NbChildrenPerNode = POW<2, dimension>::VALUE
static const HashKey	ROOT_KEY = static_cast<HashKey>(1)

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

Protected Attributes
Domain	myDomain
Node **	myData
unsigned int	myKeySize
unsigned int	myArraySize
unsigned int	myTreeDepth
unsigned int	mySpanSize
HashKey	myDepthMask
HashKey	myPreComputedIntermediateMask

Static Protected Attributes
static const unsigned int	myN = POW<2,dim>::VALUE

---

Detailed Description

template<typename TDomain, typename TValue, typename THashKey = typename DGtal::uint64_t>
class DGtal::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 124 of file ImageContainerByHashTree.h.

---

Member Typedef Documentation

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

typedef ConstRangeAdapter<typename Domain::ConstIterator, Self, Value > DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::ConstRange

Definition at line 161 of file ImageContainerByHashTree.h.

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

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

Definition at line 144 of file ImageContainerByHashTree.h.

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

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

Definition at line 139 of file ImageContainerByHashTree.h.

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

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

Definition at line 135 of file ImageContainerByHashTree.h.

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

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

Definition at line 142 of file ImageContainerByHashTree.h.

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

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

output iterator

Definition at line 164 of file ImageContainerByHashTree.h.

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

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

Definition at line 140 of file ImageContainerByHashTree.h.

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

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

Definition at line 128 of file ImageContainerByHashTree.h.

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

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

Definition at line 143 of file ImageContainerByHashTree.h.

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

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

Definition at line 160 of file ImageContainerByHashTree.h.

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

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

Definition at line 141 of file ImageContainerByHashTree.h.

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

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

Definition at line 145 of file ImageContainerByHashTree.h.

---

Constructor & Destructor Documentation

template<typename Domain , typename Value , typename HashKey >

DGtal::ImageContainerByHashTree< Domain, Value, HashKey >::ImageContainerByHashTree ( const unsigned int  hashKeySize, const unsigned int  depth, const Value  defaultValue  )

inline

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)

Definition at line 63 of file ImageContainerByHashTree.ih.

References DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::addNode(), DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::dim, DGtal::Trace::error(), DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::myArraySize, DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::myData, DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::myKeySize, DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::myOrigin, DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::myPreComputedIntermediateMask, DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::ROOT_KEY, DGtal::ImageContainerByHashTree< TDomain, TValue, THashKey >::setDepth(), and DGtal::trace.

    : myDomain( Domain() ), myKeySize ( hashKeySize )
  {

    //Consistency check of the hashKeysize
    ASSERT ( hashKeySize <= sizeof ( HashKey ) *8 );

    myOrigin = Point::zero;
    myPreComputedIntermediateMask = ~ ( static_cast<HashKey> ( ~0 ) << myKeySize );

    unsigned int acceptedDepth = ( ( sizeof ( HashKey ) * 8 - 1 ) / dim );
    if ( depth > acceptedDepth )
      {
        trace.error() << "ImageContainerByHashTree::Constructor: error !" << endl;
        trace.error() << "requested depth too high for the key type" << endl;
        trace.error() << "accepted: " << acceptedDepth << " Requested: " << depth << endl;

        setDepth ( acceptedDepth );
      }
    else
      setDepth ( depth );


    //init the array
    myArraySize = 1 << myKeySize;
    myData = new Node*[myArraySize];
    for ( unsigned i = 0; i < myArraySize; ++i )
      myData[i] = 0;
    
    addNode ( defaultValue, ROOT_KEY );
  }

template<typename Domain , typename Value , typename HashKey >

DGtal::ImageContainerByHashTree< Domain, Value, HashKey >::ImageContainerByHashTree ( const unsigned int  hashKeySize, const Point &  p1, const Point &  p2, const Value  defaultValue  )

inline

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.
p1	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)

Definition at line 147 of file ImageContainerByHashTree.ih.

References DGtal::Trace::error(), and DGtal::trace.

    : myDomain( p1, p2 ), myKeySize ( hashKeySize ), myOrigin ( p1 )
  {
    //Consistency check of the hashKeysize
    ASSERT ( hashKeySize <= sizeof ( HashKey ) *8 );
    
    myPreComputedIntermediateMask = ~ ( static_cast<HashKey> ( ~0 ) << myKeySize );
    
    int maxSize = 0;
    for ( unsigned int i = 0; i < dim; ++i )
      if ( maxSize < p1[i] - p2[i] )
        maxSize = p1[i] - p2[i];
    unsigned int depth = (unsigned int)(ceil ( log ( (double) maxSize ) / log((double) 2.0) ));
    
    unsigned int  acceptedDepth = ( ( sizeof ( HashKey ) * 8 - 1 ) / dim );
    if ( depth > acceptedDepth )
      {
        trace.error() << "ImageContainerByHashTree::Constructor: error !"
                      << " requested depth too high for the key type" << endl;
        trace.error() << "accepted: " << acceptedDepth 
                      << " Requested: " << depth << endl;
        setDepth ( acceptedDepth );
      }
    else
      setDepth ( depth );

    //init the array
    myArraySize = 1 << hashKeySize;
    myData = new Node*[myArraySize];
    for ( unsigned int i = 0; i < myArraySize; ++i )
      myData[i] = 0;
    //add the default value
    addNode ( defaultValue, ROOT_KEY );
  }

template<typename Domain , typename Value , typename HashKey >

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

inline

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)

Definition at line 101 of file ImageContainerByHashTree.ih.

References DGtal::Trace::error(), and DGtal::trace.

                                                         :
    myDomain(aDomain),  myKeySize ( hashKeySize )
  {
    myOrigin = aDomain.lowerBound() ;
    //Consistency check of the hashKeysize
    ASSERT ( hashKeySize <= sizeof ( HashKey ) *8 );
    
    Point p1 = myDomain.lowerBound();
    Point p2 = myDomain.upperBound();

    myPreComputedIntermediateMask = ~ ( static_cast<HashKey> ( ~0 ) << myKeySize );
    
    int maxSize = 0;
    for ( unsigned int i = 0; i < dim; ++i )
      if ( maxSize < p1[i] - p2[i] )
        maxSize = p1[i] - p2[i];
    unsigned int depth = (unsigned int)(ceil ( log ( (double) maxSize ) / log((double) 2.0) ));
    
    unsigned int  acceptedDepth = ( ( sizeof ( HashKey ) * 8 - 1 ) / dim );
    if ( depth > acceptedDepth )
      {
        trace.error() << "ImageContainerByHashTree::Constructor: error !"
                      << " requested depth too high for the key type" << endl;
        trace.error() << "accepted: " << acceptedDepth 
                      << " Requested: " << depth << endl;
        setDepth ( acceptedDepth );
      }
    else
      setDepth ( depth );

    //init the array
    myArraySize = 1 << hashKeySize;
    myData = new Node*[myArraySize];
    for ( unsigned int i = 0; i < myArraySize; ++i )
      myData[i] = 0;
    //add the default value
    addNode ( defaultValue, ROOT_KEY );