DGtal  1.5.beta
ImageContainerByHashTree.ih
1 
2 /**
3  * This program is free software: you can redistribute it and/or modify
4  * it under the terms of the GNU Lesser General Public License as
5  * published by the Free Software Foundation, either version 3 of the
6  * License, or (at your option) any later version.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11  * GNU General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public License
14  * along with this program. If not, see <http://www.gnu.org/licenses/>.
15  *
16  **/
17 
18 /**
19  * @file ImageContainerByHashTree.ih
20  * @author Nicolas Silva (\c nicolas.silva@insa-lyon.fr )
21  * @author David Coeurjolly (\c david.coeurjolly@liris.cnrs.fr )
22  * Laboratoire d'InfoRmatique en Image et Systèmes d'information - LIRIS (CNRS, UMR 5205), CNRS, France
23  *
24  * @date 2010/09/02
25  *
26  * Implementation of inline methods defined in ImageContainerByHashTree.h
27  *
28  * This file is part of the DGtal library.
29  */
30 
31 
32 //////////////////////////////////////////////////////////////////////////////
33 #include <cstdlib>
34 
35 #include <cmath>
36 #include <assert.h>
37 #include <list>
38 #include <stdlib.h>
39 
40 #include <sstream>
41 #include <iostream>
42 
43 //////////////////////////////////////////////////////////////////////////////
44 
45 ///////////////////////////////////////////////////////////////////////////////
46 // IMPLEMENTATION of inline methods.
47 ///////////////////////////////////////////////////////////////////////////////
48 
49 ///////////////////////////////////////////////////////////////////////////////
50 // ----------------------- Standard services ------------------------------
51 namespace DGtal
52 {
53 
54  namespace experimental
55  {
56 
57  // ---------------------------------------------------------------------
58  // constructor
59  // ---------------------------------------------------------------------
60 
61  template < typename Domain, typename Value, typename HashKey>
62  inline
63  ImageContainerByHashTree<Domain, Value, HashKey>
64  ::ImageContainerByHashTree ( const unsigned int hashKeySize,
65  const unsigned int depth,
66  const Value defaultValue )
67  : myKeySize ( hashKeySize )
68  {
69 
70  //Consistency check of the hashKeysize
71  ASSERT ( hashKeySize <= sizeof ( HashKey ) *8 );
72 
73  myOrigin = Point::zero;
74  myPreComputedIntermediateMask = ~ ( static_cast<HashKey> ( ~0 ) << myKeySize );
75 
76  unsigned int acceptedDepth = ( ( sizeof ( HashKey ) * 8 - 2 ) / dim );
77  unsigned int acceptedDomainDepth = ( sizeof ( typename Domain::Point::Coordinate ) * 8 - 1 );
78  if (( depth > acceptedDepth ) || (depth > acceptedDomainDepth))
79  {
80  trace.error() << "ImageContainerByHashTree::Constructor: error !" << std::endl;
81  trace.error() << "requested depth too high for the key type" << std::endl;
82  trace.error() << "accepted: " << acceptedDepth << " accepted (Domain): "<<acceptedDomainDepth<<" Requested: " << depth << std::endl;
83 
84  setDepth ( ( acceptedDepth < acceptedDomainDepth) ? acceptedDepth -1 : acceptedDomainDepth -1 );
85  }
86  else
87  setDepth ( depth );
88 
89  myDomain = Domain(Point::zero, Point::diagonal(static_cast<typename Point::Component>( pow(2.0, (int)myTreeDepth) )));
90 
91  //init the array
92  myArraySize = 1 << myKeySize;
93  myData = new Node*[myArraySize];
94  for ( unsigned i = 0; i < myArraySize; ++i )
95  myData[i] = 0;
96 
97  addNode ( defaultValue, ROOT_KEY );
98  }
99 
100 
101  template < typename Domain, typename Value, typename HashKey>
102  inline
103  ImageContainerByHashTree<Domain, Value, HashKey>
104  ::ImageContainerByHashTree ( const Domain &aDomain,
105  const unsigned int hashKeySize,
106  const Value defaultValue ):
107  myDomain(aDomain), myKeySize ( hashKeySize )
108  {
109  myOrigin = aDomain.lowerBound() ;
110  //Consistency check of the hashKeysize
111  ASSERT ( hashKeySize <= sizeof ( HashKey ) *8 );
112 
113  Point p1 = myDomain.lowerBound();
114  Point p2 = myDomain.upperBound();
115 
116  myPreComputedIntermediateMask = ~ ( static_cast<HashKey> ( ~0 ) << myKeySize );
117 
118  typename Point::Component maxSize = (p2-p1).normInfinity();
119  unsigned int depth = (unsigned int)(ceil ( log2 ( (double) maxSize ))) ;
120 
121  unsigned int acceptedDepth = ( ( sizeof ( HashKey ) * 8 - 1 ) / dim );
122  if ( depth > acceptedDepth )
123  {
124  trace.error() << "ImageContainerByHashTree::Constructor: error !"
125  << " requested depth too high for the key type" << std::endl;
126  trace.error() << "accepted: " << acceptedDepth
127  << " Requested: " << depth << std::endl;
128  setDepth ( acceptedDepth );
129  }
130  else
131  setDepth ( depth );
132 
133  //init the array
134  myArraySize = 1 << hashKeySize;
135  myData = new Node*[myArraySize];
136  for ( unsigned int i = 0; i < myArraySize; ++i )
137  myData[i] = 0;
138  //add the default value
139  addNode ( defaultValue, ROOT_KEY );
140  }
141 
142 
143 
144  template < typename Domain, typename Value, typename HashKey>
145  inline
146  ImageContainerByHashTree<Domain, Value, HashKey>
147  ::ImageContainerByHashTree ( const unsigned int hashKeySize,
148  const Point & p1,
149  const Point & p2,
150  const Value defaultValue )
151  : myDomain( p1, p2 ), myKeySize ( hashKeySize ), myOrigin ( p1 )
152  {
153  //Consistency check of the hashKeysize
154  ASSERT ( hashKeySize <= sizeof ( HashKey ) *8 );
155 
156  myPreComputedIntermediateMask = ~ ( static_cast<HashKey> ( ~0 ) << myKeySize );
157 
158  int maxSize = 0;
159  for ( unsigned int i = 0; i < dim; ++i )
160  if ( maxSize < p1[i] - p2[i] )
161  maxSize = p1[i] - p2[i];
162  unsigned int depth = (unsigned int)(ceil ( log ( (double) maxSize ) / log((double) 2.0) ));
163 
164  unsigned int acceptedDepth = ( ( sizeof ( HashKey ) * 8 - 1 ) / dim );
165  if ( depth > acceptedDepth )
166  {
167  trace.error() << "ImageContainerByHashTree::Constructor: error !"
168  << " requested depth too high for the key type" << std::endl;
169  trace.error() << "accepted: " << acceptedDepth
170  << " Requested: " << depth << std::endl;
171  setDepth ( acceptedDepth );
172  }
173  else
174  setDepth ( depth );
175 
176  //init the array
177  myArraySize = 1 << hashKeySize;
178  myData = new Node*[myArraySize];
179  for ( unsigned int i = 0; i < myArraySize; ++i )
180  myData[i] = 0;
181  //add the default value
182  addNode ( defaultValue, ROOT_KEY );
183  }
184 
185 
186  // ---------------------------------------------------------------------
187  // access methods
188  // ---------------------------------------------------------------------
189 
190  //------------------------------------------------------------------------------
191  template < typename Domain, typename Value, typename HashKey>
192  inline
193  const typename ImageContainerByHashTree<Domain, Value, HashKey >::Domain&
194  ImageContainerByHashTree<Domain, Value, HashKey >::domain() const
195  {
196  return myDomain;
197  }
198 
199  //------------------------------------------------------------------------------
200  template < typename Domain, typename Value, typename HashKey>
201  inline
202  typename ImageContainerByHashTree<Domain, Value, HashKey >::ConstRange
203  ImageContainerByHashTree<Domain, Value, HashKey >::constRange() const
204  {
205  return ConstRange( *this );
206  }
207  //------------------------------------------------------------------------------
208  template < typename Domain, typename Value, typename HashKey>
209  inline
210  typename ImageContainerByHashTree<Domain, Value, HashKey >::Range
211  ImageContainerByHashTree<Domain, Value, HashKey >::range()
212  {
213  return Range( *this );
214  }
215 
216  //------------------------------------------------------------------------------
217  /*template < typename Domain, typename Value, typename HashKey>
218  inline
219  typename ImageContainerByHashTree<Domain, Value, HashKey >::OutputIterator
220  ImageContainerByHashTree<Domain, Value, HashKey >::outputIterator()
221  {
222  return OutputIterator( *this );
223  }*/
224 
225 
226  template < typename Domain, typename Value, typename HashKey>
227  inline
228  void
229  ImageContainerByHashTree<Domain, Value, HashKey >::setValue ( const Point& aPoint, const Value value )
230  {
231  setValue ( getKey ( aPoint ), value );
232  }
233 
234 
235  template < typename Domain, typename Value, typename HashKey>
236  inline
237  void
238  ImageContainerByHashTree<Domain, Value, HashKey >::setValue ( const HashKey key, const Value value )
239  {
240  HashKey brothers[myN-1];
241 
242  bool broValue = ( key != static_cast<HashKey> ( 1 ) );
243  myMorton.brotherKeys ( key, brothers );
244  for ( unsigned int i = 0; i < myN - 1; ++ i )
245  {
246  Node* n = getNode ( brothers[i] );
247  if ( ! ( n && ( n->getObject() == value ) ) )
248  {
249  broValue = false;
250  break;
251  }
252  }
253 
254  if ( broValue )
255  {
256  setValue ( myMorton.parentKey ( key ), value );
257  return;
258  }
259 
260  // if the key already exists
261  Node* n = getNode ( key );
262  if ( n )
263  {
264  n->getObject() = value;
265  return;
266  }
267 
268  //if there's a leaf above the requested node
269  HashKey iterKey = key;
270  std::list< HashKey > nodeList;
271  while ( iterKey != 0 )
272  {
273  // cerr << "while(iter)..." << std::endl;
274  n = getNode ( iterKey );
275  if ( n )
276  {
277  Value tempVal = n->getObject();
278  if ( tempVal == value )
279  return;
280  removeNode ( iterKey );
281  for ( typename std::list< HashKey >::iterator it = nodeList.begin();
282  it != nodeList.end();
283  it++ )
284  {
285  // cerr << "adding a node ("<< bits::bitString(*it, 8)<<")" << std::endl;
286  addNode ( tempVal, *it );
287  }
288  addNode ( value, key );
289  //cerr << "return " << std::endl;
290  return;
291  }
292  else
293  {
294  //cerr << " + " << std::endl;
295  HashKey brothersH[myN-1];
296  myMorton.brotherKeys ( iterKey, brothersH );
297  for ( unsigned int i = 0; i < myN - 1; ++i )
298  {
299  nodeList.push_front ( brothersH[i] );
300  }
301  }
302  iterKey >>= dim;
303  }
304  addNode ( value, key );
305  unsigned int nbRecur = myTreeDepth - getKeyDepth ( key ) + 1;
306  HashKey children[myN];
307  myMorton.childrenKeys ( key, children );
308  for ( unsigned int i = 0; i < myN; ++i )
309  recursiveRemoveNode ( children[i], nbRecur );
310 
311  return;
312 
313  }
314 
315  template < typename Domain, typename Value, typename HashKey >
316  inline
317  Value ImageContainerByHashTree<Domain, Value, HashKey >::operator() ( const HashKey key ) const
318  {
319  return get ( key );
320  }
321  template < typename Domain, typename Value, typename HashKey >
322  inline
323  Value ImageContainerByHashTree<Domain, Value, HashKey >::operator() ( const Point &aPoint ) const
324  {
325  return get ( aPoint );
326  }
327 
328  template < typename Domain, typename Value, typename HashKey >
329  inline
330  Value ImageContainerByHashTree<Domain, Value, HashKey >::get ( const HashKey key ) const
331  {
332 
333  HashKey iterKey = key;
334  // node above the requested node
335  while ( iterKey != 0 )
336  {
337  Node* n = getNode ( iterKey );
338  if ( n )
339  return n->getObject();
340  iterKey >>= dim;
341  }
342  //if the node is deeper than the one requested
343  return blendChildren ( key );
344  }
345 
346 
347  template < typename Domain, typename Value, typename HashKey >
348  inline
349  Value ImageContainerByHashTree<Domain, Value, HashKey >::reverseGet ( const HashKey key ) const
350  {
351 
352  HashKey iterKey = key;
353  // node above the requested node
354  HashKey limit = myDepthMask << 1;
355  while ( iterKey < limit )
356  {
357  Node* n = getNode ( iterKey );
358  if ( n )
359  return blendChildren ( key );
360  iterKey <<= dim;
361  }
362  iterKey = key;
363  while ( iterKey != 0 )
364  {
365  Node* n = getNode ( iterKey );
366  if ( n )
367  return n->getObject();
368  iterKey >>= dim;
369  }
370  return 0;
371  }
372 
373 
374  template < typename Domain, typename Value, typename HashKey>
375  inline
376  Value
377  ImageContainerByHashTree<Domain, Value, HashKey >::get ( const Point & aPoint ) const
378  {
379  return get ( getKey ( aPoint ) );
380  }
381 
382  //Deprecated
383  template < typename Domain, typename Value, typename HashKey >
384  inline
385  Value
386  ImageContainerByHashTree<Domain, Value, HashKey >::upwardGet ( const HashKey key ) const
387  {
388  //cerr << "ImageContainerByHashTree::upWardGet" << std::endl;
389  HashKey aKey = key;
390 
391  while ( aKey )
392  {
393  HashKey key2 = getIntermediateKey ( aKey );
394  Node* iter = myData[key2];
395 
396  while ( iter != 0 )
397  {
398  if ( iter->getKey() == aKey )
399  return iter->getObject();
400  iter = iter->getNext();
401  }
402  aKey >>= dim; // transorm the key to search in an upper level
403  }
404  }
405 
406  template < typename Domain, typename Value, typename HashKey >
407  inline
408  HashKey
409  ImageContainerByHashTree<Domain, Value, HashKey >::getKey ( const Point & aPoint ) const
410  {
411  HashKey result = 0;
412  Point currentPos = aPoint - myOrigin;
413 
414  myMorton.interleaveBits ( currentPos, result );
415  // by convention, the root node has the key 0..01
416  // it makes it easy to determine the depth of a node by it's key (looking
417  // at the position of the most significant bit that is equal to 1)
418  result |= myDepthMask;
419 
420  return result;
421  }
422 
423  template < typename Domain, typename Value, typename HashKey >
424  inline
425  HashKey
426  ImageContainerByHashTree<Domain, Value, HashKey >::getIntermediateKey ( HashKey key ) const
427  {
428  return ( key & myPreComputedIntermediateMask );
429  }
430 
431 
432  template < typename Domain, typename Value, typename HashKey >
433  inline
434  bool
435  ImageContainerByHashTree<Domain, Value, HashKey >::Iterator::next()
436  {
437  if ( myNode )
438  {
439  myNode = myNode->getNext();
440  if ( myNode )
441  {
442  return true;
443  }
444  else
445  {
446  do
447  {
448  myNode = myContainerData[++myCurrentCell];
449  if ( myCurrentCell >= myArraySize )
450  return false;
451  }
452  while ( !myNode );
453  return true;
454  }
455  }
456  return false;
457  }
458 
459  // ---------------------------------------------------------------------
460  //
461  // ---------------------------------------------------------------------
462 
463  template < typename Domain, typename Value, typename HashKey >
464  inline
465  bool
466  ImageContainerByHashTree<Domain, Value, HashKey >::removeNode ( HashKey key )
467  {
468  HashKey key2 = getIntermediateKey ( key );
469  Node* iter = myData[key2];
470  // if the node is the first in the list we have to modify the pointer stored in myData
471  if ( iter && ( iter->getKey() == key ) )
472  {
473  myData[key2] = iter->getNext();
474  delete iter;
475  return true;
476  }
477  while ( iter )
478  {
479  Node* next = iter->getNext();
480  if ( next )
481  {
482  if ( next->getKey() == key )
483  {
484  iter->setNext ( next->getNext() );
485  delete next;
486  return true;
487  }
488  }
489  iter = iter->getNext();
490  }
491  return false;
492  }
493 
494  template < typename Domain, typename Value, typename HashKey >
495  inline
496  void
497  ImageContainerByHashTree<Domain, Value, HashKey >::recursiveRemoveNode ( HashKey key, unsigned int nbRecursions )
498  {
499  if ( removeNode ( key ) )
500  return;
501  if ( --nbRecursions > 0 )
502  {
503  HashKey children[myN];
504  myMorton.childrenKeys ( key, children );
505  for ( unsigned int i = 0; i < myN; ++i )
506  {
507  recursiveRemoveNode ( children[i], nbRecursions );
508  }
509  }
510  }
511 
512 
513 
514  // ---------------------------------------------------------------------
515  //
516  // ---------------------------------------------------------------------
517 
518  template < typename Domain, typename Value, typename HashKey >
519  inline
520  void
521  ImageContainerByHashTree<Domain, Value, HashKey >::setDepth ( unsigned int depth )
522  {
523  myTreeDepth = depth;
524  mySpanSize = 1 << depth;
525  //precompute the mask
526  myDepthMask = static_cast<HashKey> ( 1 ) << dim * depth;
527  }
528 
529 
530  template < typename Domain, typename Value, typename HashKey >
531  inline
532  unsigned int
533  ImageContainerByHashTree<Domain, Value, HashKey >::getKeyDepth ( HashKey key ) const
534  {
535  for ( int i = ( sizeof ( HashKey ) << 3 ) - 1; i >= 0; --i )
536  if ( key & ( static_cast<HashKey> ( 1 ) << i ) )
537  {
538  return ( i ) / dim;
539  }
540  return 0;
541  }
542 
543 
544  template < typename Domain, typename Value, typename HashKey >
545  inline
546  int*
547  ImageContainerByHashTree<Domain, Value, HashKey >::getCoordinatesFromKey ( HashKey key ) const
548  {
549  //remove the first bit equal 1
550  for ( int i = ( sizeof ( HashKey ) << 3 ) - 1; i >= 0; --i )
551  {
552  if ( key & Bits::mask<HashKey> ( i ) )
553  {
554  key &= ~Bits::mask<HashKey> ( i );
555  break;
556  }
557  }
558  int* coordinates = new int[dim];
559  //deinterleave the bits
560  for ( unsigned int i = 0; i < dim; ++i )
561  {
562  coordinates[i] = 0;
563  for ( unsigned int bitPos = 0; bitPos < ( sizeof ( HashKey ) << 3 ) / dim; ++bitPos )
564  {
565  if ( key & Bits::mask ( bitPos*dim + i ) )
566  {
567  coordinates[i] |= Bits::mask<HashKey> ( bitPos );
568  }
569  }
570  }
571  return coordinates;
572  }
573 
574 
575  template < typename Domain, typename Value, typename HashKey >
576  inline
577  bool
578  ImageContainerByHashTree<Domain, Value, HashKey >::isKeyValid ( HashKey key ) const
579  {
580  if ( !key )
581  return false;
582  if ( getKeyDepth ( key ) > myTreeDepth )
583  return false;
584 
585  int i = ( sizeof ( HashKey ) << 3 ) - 1;
586  for ( ; i >= 0; --i )
587  if ( key & ( static_cast<HashKey> ( 1 ) << i ) )
588  break;
589 
590  if ( i % dim )
591  {
592  return false;
593  }
594 
595  return true;
596  }
597 
598 
599  // ---------------------------------------------------------------------
600  // Debug
601  // ---------------------------------------------------------------------
602  template <typename Domain, typename Value , typename HashKey >
603  inline
604  void
605  ImageContainerByHashTree<Domain, Value, HashKey >::printState ( std::ostream& out, bool displayKeys ) const
606  {
607  out << "ImageContainerByHashTree::printState" << std::endl;
608  out << "depth: " << myTreeDepth << " (" << Bits::bitString ( myDepthMask ) << ")" << std::endl;
609  out << "dim: " << dim << "myN: " << myN << std::endl;
610  printTree ( ROOT_KEY, out, displayKeys );
611  }
612 
613  template <typename Domain, typename Value, typename HashKey >
614  inline
615  void
616  ImageContainerByHashTree<Domain, Value, HashKey >::printTree ( HashKey key, std::ostream& out, bool displayKeys ) const
617  {
618  unsigned int level = getKeyDepth ( key );
619  for ( unsigned int i = 0; i < level; ++i )
620  out << " ";
621  Node* n = getNode ( key );
622  if ( n )
623  {
624  out << " < " << n->getObject() << " > ";
625  if ( displayKeys )
626  out << Bits::bitString ( key, 8 );
627  out << std::endl;
628  }
629  else
630  {
631  out << " < x > ";
632  if ( displayKeys )
633  out << Bits::bitString ( key, 8 );
634  out << std::endl;
635  }
636 
637  if ( level < myTreeDepth )
638  {
639  HashKey children[myN];
640  myMorton.childrenKeys ( key, children );
641  for ( unsigned int i = 0; i < myN; ++i )
642  printTree ( children[i], out, displayKeys );
643  }
644  }
645 
646  template <typename Domain, typename Value, typename HashKey >
647  inline
648  void
649  ImageContainerByHashTree<Domain, Value, HashKey >::printInternalState ( std::ostream& out, unsigned int nbBits ) const
650  {
651  out << "ImageContainerByHashTree::printInternalState ----------------------------------" << std::endl;
652  out << "| <template> dim = " << dim << " myN = " << myN << std::endl;
653  out << "| tree depth = " << myTreeDepth << " mask = " << Bits::bitString ( myDepthMask ) << std::endl;
654 
655  for ( unsigned int i = 0; i < ( 1 << myKeySize ); ++i )
656  {
657  out << "| " << Bits::bitString ( i, myKeySize ) << " [";
658  if ( myData[i] )
659  {
660  out << "-]->(";
661  if ( nbBits )
662  out << Bits::bitString ( myData[i]->getKey(), nbBits ) << ":";
663  out << myData[i]->getObject() << ")";
664  Node* iter = myData[i]->getNext();
665  while ( iter )
666  {
667  out << "->(";
668  if ( nbBits )
669  out << Bits::bitString ( myData[i]->getKey(), nbBits ) << ":";
670  out << iter->getObject() << ")";
671  iter = iter->getNext();
672  }
673  out << std::endl;
674  }
675  else
676  {
677  std::cout << "x]" << std::endl;
678  }
679  }
680 
681  out << "| image size: " << getSpanSize() << "^" << dim << " (" << std::pow ( getSpanSize(), dim ) *sizeof ( Value ) << " bytes)" << std::endl;
682  out << "| " << getNbNodes() << " nodes - Empty lists: " << getNbEmptyLists() << " (" << getNbEmptyLists() *sizeof ( Node* ) << " bytes)" << std::endl;
683  out << "| Average collisions: " << getAverageCollisions() << " - Max collisions " << getMaxCollisions() << std::endl;
684  out << "----------------------------------------------------------------" << std::endl;
685  }
686 
687 
688  template <typename Domain, typename Value, typename HashKey >
689  inline
690  void
691  ImageContainerByHashTree<Domain, Value, HashKey >::printInfo ( std::ostream& out ) const
692  {
693  unsigned int nbNodes = getNbNodes();
694  unsigned int totalSize = sizeof ( *this ) + ( 1 << myKeySize ) * sizeof ( Node* ) + nbNodes * sizeof ( Node );
695 
696  out << "[ImageContainerByHashTree]: Dimension=" << ( int ) dim << ", HashKey size="
697  << myKeySize << ", Depth=" << myTreeDepth << ", image size=" << getSpanSize()
698  << "^" << ( int ) dim << " (" << std::pow ( ( double ) getSpanSize(), ( double ) dim ) *sizeof ( Value )
699  << " bytes)" << ", " << nbNodes << " nodes" << ", Empty lists=" << getNbEmptyLists()
700  << " (" << getNbEmptyLists() *sizeof ( Node* ) << " bytes)" << ", Average collisions=" << getAverageCollisions()
701  << ", Max collisions " << getMaxCollisions()
702  << ", total memory usage=" << totalSize << " bytes" << std::endl;
703  }
704 
705 
706 
707  template <typename Domain, typename Value, typename HashKey >
708  inline
709  unsigned int
710  ImageContainerByHashTree<Domain, Value, HashKey >::getNbNodes ( unsigned int intermediateKey ) const
711  {
712  if ( !myData[intermediateKey] )
713  {
714  return 0;
715  }
716  else
717  {
718  unsigned int count = 1;
719  Node* n = myData[intermediateKey]->getNext();
720  while ( n )
721  {
722  ++count;
723  n = n->getNext();
724  }
725  return count;
726  }
727  }
728 
729 
730 
731  template <typename Domain, typename Value, typename HashKey >
732  inline
733  unsigned int
734  ImageContainerByHashTree<Domain, Value, HashKey >::getNbNodes() const
735  {
736  unsigned int count = 0;
737  unsigned int arraySize = 1 << myKeySize;
738  for ( unsigned int i = 0; i < arraySize; ++i )
739  {
740  count += getNbNodes ( i );
741  }
742  return count;
743  }
744 
745 
746  template <typename Domain, typename Value, typename HashKey >
747  inline
748  unsigned int
749  ImageContainerByHashTree<Domain, Value, HashKey >::getNbEmptyLists() const
750  {
751  unsigned int count = 0;
752  unsigned int arraySize = 1 << myKeySize;
753  for ( unsigned int i = 0; i < arraySize; ++i )
754  {
755  if ( !myData[i] )
756  count++;
757  }
758  return count;
759  }
760 
761 
762  template<typename Domain, typename Value, typename HashKey >
763  inline
764  double
765  ImageContainerByHashTree<Domain, Value, HashKey >::getAverageCollisions() const
766  {
767  double count = 0;
768  double nbLists = 0;
769  unsigned int arraySize = 1 << myKeySize;
770  for ( unsigned int i = 0; i < arraySize; ++i )
771  {
772  if ( myData[i] )
773  {
774  count += getNbNodes ( i ) - 1;
775  nbLists++;
776  }
777  }
778  if ( nbLists == 0 )
779  {
780  trace.error() << "ImageContainerByHashTree::getAverageCollision() - error" << std::endl
781  << "the container is empty !" << std::endl;
782  return 0;
783  }
784  return count / nbLists;
785  }
786 
787 
788 
789  template <typename Domain, typename Value, typename HashKey >
790  inline
791  unsigned int
792  ImageContainerByHashTree<Domain, Value, HashKey >::getMaxCollisions() const
793  {
794  unsigned int count = 0;
795  unsigned int arraySize = 1 << myKeySize;
796  for ( unsigned int i = 0; i < arraySize; ++i )
797  {
798  if ( myData[i] )
799  {
800  unsigned int collision = getNbNodes ( i ) - 1;
801  if ( collision > count )
802  {
803  count = collision;
804  }
805  }
806  }
807  return count;
808  }
809 
810  //------------------------------------------------------------------------------
811  template <typename Domain, typename Value, typename HashKey >
812  inline
813  std::string
814  ImageContainerByHashTree<Domain, Value, HashKey >::className() const
815  {
816  return "ImageContainerByHashTree";
817  }
818 
819  template <typename Domain, typename Value, typename HashKey >
820  Value
821  ImageContainerByHashTree<Domain, Value, HashKey >::blendChildren ( HashKey key ) const
822  {
823  Node* n = getNode ( key );
824  if ( n )
825  {
826  return n->getObject();
827  }
828  else
829  {
830  HashKey children[myN];
831  myMorton.childrenKeys ( key, children );
832  float result = 0;
833  for ( unsigned int i = 0; i < myN; ++i )
834  {
835  result += blendChildren ( children[i] );
836  }
837  return static_cast<Value> ( result / myN );
838  }
839  }
840 
841 
842  template <typename Domain, typename Value, typename HashKey >
843  bool
844  ImageContainerByHashTree<Domain, Value, HashKey >::checkIntegrity ( HashKey key, bool leafAbove ) const
845  {
846  trace.info() << "Checking key=" << key << std::endl;
847  if ( !isKeyValid ( key ) )
848  {
849  trace.error() << "checkIntegrity->invalid key " << Bits::bitString ( key );
850  trace.info() << std::endl;
851  ASSERT ( 1 == 0 );
852  }
853 
854  Node* n = getNode ( key );
855 
856  if ( ( n != 0 ) && ( leafAbove ) )
857  {
858  trace.error() << "ImageContainerByHashTree::checkIntegrity - error:" << std::endl
859  << "at key " << Bits::bitString ( key ) << std::endl
860  << "several leafs found" << std::endl;
861  return false;
862  }
863 
864  if ( getKeyDepth ( key ) >= myTreeDepth )
865  {
866  if ( leafAbove || n )
867  {
868  return true;
869  }
870  else
871  {
872  trace.error() << "ImageContainerByHashTree::checkIntegrity - error:" << std::endl
873  << "at key " << Bits::bitString ( key ) << std::endl
874  << "no leaf found" << std::endl;
875  return false;
876  }
877  }
878 
879  HashKey children[myN];
880  myMorton.childrenKeys ( key, children );
881  bool returnValue = true;
882  for ( unsigned int i = 0; i < myN; ++i )
883  returnValue &= checkIntegrity ( children[i], ( n || leafAbove ) );
884  return returnValue;
885  }
886 
887 
888 
889 
890  ///////////////////////////////////////////////////////////////////////////////
891  // Interface - public :
892 
893  /**
894  * Writes/Displays the object on an output stream.
895  * @param out the output stream where the object is written.
896  */
897  template < typename Domain, typename Value, typename HashKey>
898  inline
899  void
900  ImageContainerByHashTree< Domain, Value, HashKey>::selfDisplay ( std::ostream & out ) const
901  {
902  printInfo ( out );
903  }
904 }
905 } // namespace DGtal
906 // //
907 ///////////////////////////////////////////////////////////////////////////////