DGtal  0.6.devel
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
ImageContainerByHashTree.ih
1 
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 using namespace std;
46 
48 // IMPLEMENTATION of inline methods.
50 
52 // ----------------------- Standard services ------------------------------
53 namespace DGtal
54 {
55 
56  // ---------------------------------------------------------------------
57  // constructor
58  // ---------------------------------------------------------------------
59 
60  template < typename Domain, typename Value, typename HashKey>
61  inline
62  ImageContainerByHashTree<Domain, Value, HashKey>
63  ::ImageContainerByHashTree ( const unsigned int hashKeySize,
64  const unsigned int depth,
65  const Value defaultValue )
66  : myDomain( Domain() ), myKeySize ( hashKeySize )
67  {
68 
69  //Consistency check of the hashKeysize
70  ASSERT ( hashKeySize <= sizeof ( HashKey ) *8 );
71 
72  myOrigin = Point::zero;
73  myPreComputedIntermediateMask = ~ ( static_cast<HashKey> ( ~0 ) << myKeySize );
74 
75  unsigned int acceptedDepth = ( ( sizeof ( HashKey ) * 8 - 1 ) / dim );
76  if ( depth > acceptedDepth )
77  {
78  trace.error() << "ImageContainerByHashTree::Constructor: error !" << endl;
79  trace.error() << "requested depth too high for the key type" << endl;
80  trace.error() << "accepted: " << acceptedDepth << " Requested: " << depth << endl;
81 
82  setDepth ( acceptedDepth );
83  }
84  else
85  setDepth ( depth );
86 
87 
88  //init the array
89  myArraySize = 1 << myKeySize;
90  myData = new Node*[myArraySize];
91  for ( unsigned i = 0; i < myArraySize; ++i )
92  myData[i] = 0;
93 
94  addNode ( defaultValue, ROOT_KEY );
95  }
96 
97 
98  template < typename Domain, typename Value, typename HashKey>
99  inline
100  ImageContainerByHashTree<Domain, Value, HashKey>
101  ::ImageContainerByHashTree ( const Domain &aDomain,
102  const unsigned int hashKeySize,
103  const Value defaultValue ):
104  myDomain(aDomain), myKeySize ( hashKeySize )
105  {
106  myOrigin = aDomain.lowerBound() ;
107  //Consistency check of the hashKeysize
108  ASSERT ( hashKeySize <= sizeof ( HashKey ) *8 );
109 
110  Point p1 = myDomain.lowerBound();
111  Point p2 = myDomain.upperBound();
112 
113  myPreComputedIntermediateMask = ~ ( static_cast<HashKey> ( ~0 ) << myKeySize );
114 
115  int maxSize = 0;
116  for ( unsigned int i = 0; i < dim; ++i )
117  if ( maxSize < p1[i] - p2[i] )
118  maxSize = p1[i] - p2[i];
119  unsigned int depth = (unsigned int)(ceil ( log ( (double) maxSize ) / log((double) 2.0) ));
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" << endl;
126  trace.error() << "accepted: " << acceptedDepth
127  << " Requested: " << depth << 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" << endl;
169  trace.error() << "accepted: " << acceptedDepth
170  << " Requested: " << depth << 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 >::range() const
204  {
205  return ConstRange( myDomain.begin(), myDomain.end(), *this );
206  }
207 
208  //------------------------------------------------------------------------------
209  template < typename Domain, typename Value, typename HashKey>
210  inline
211  typename ImageContainerByHashTree<Domain, Value, HashKey >::OutputIterator
212  ImageContainerByHashTree<Domain, Value, HashKey >::outputIterator()
213  {
214  return OutputIterator( *this );
215  }
216 
217 
218  template < typename Domain, typename Value, typename HashKey>
219  inline
220  void
221  ImageContainerByHashTree<Domain, Value, HashKey >::setValue ( const Point& aPoint, const Value value )
222  {
223  setValue ( getKey ( aPoint ), value );
224  }
225 
226 
227  template < typename Domain, typename Value, typename HashKey>
228  inline
229  void
230  ImageContainerByHashTree<Domain, Value, HashKey >::setValue ( const HashKey key, const Value value )
231  {
232  HashKey brothers[myN-1];
233 
234  bool broValue = ( key != static_cast<HashKey> ( 1 ) );
235  myMorton.brotherKeys ( key, brothers );
236  for ( unsigned int i = 0; i < myN - 1; ++ i )
237  {
238  Node* n = getNode ( brothers[i] );
239  if ( ! ( n && ( n->getObject() == value ) ) )
240  {
241  broValue = false;
242  break;
243  }
244  }
245 
246  if ( broValue )
247  {
248  setValue ( myMorton.parentKey ( key ), value );
249  return;
250  }
251 
252  // if the key already exists
253  Node* n = getNode ( key );
254  if ( n )
255  {
256  n->getObject() = value;
257  return;
258  }
259 
260  //if there's a leaf above the requested node
261  HashKey iterKey = key;
262  std::list< HashKey > nodeList;
263  while ( iterKey != 0 )
264  {
265  // cerr << "while(iter)..." << endl;
266  n = getNode ( iterKey );
267  if ( n )
268  {
269  Value tempVal = n->getObject();
270  if ( tempVal == value )
271  return;
272  removeNode ( iterKey );
273  for ( typename std::list< HashKey >::iterator it = nodeList.begin();
274  it != nodeList.end();
275  it++ )
276  {
277  // cerr << "adding a node ("<< bits::bitString(*it, 8)<<")" << endl;
278  addNode ( tempVal, *it );
279  }
280  addNode ( value, key );
281  //cerr << "return " << endl;
282  return;
283  }
284  else
285  {
286  //cerr << " + " << endl;
287  HashKey brothersH[myN-1];
288  myMorton.brotherKeys ( iterKey, brothersH );
289  for ( unsigned int i = 0; i < myN - 1; ++i )
290  {
291  nodeList.push_front ( brothersH[i] );
292  }
293  }
294  iterKey >>= dim;
295  }
296  addNode ( value, key );
297  unsigned int nbRecur = myTreeDepth - getKeyDepth ( key ) + 1;
298  HashKey children[myN];
299  myMorton.childrenKeys ( key, children );
300  for ( unsigned int i = 0; i < myN; ++i )
301  recursiveRemoveNode ( children[i], nbRecur );
302 
303  return;
304 
305  }
306 
307  template < typename Domain, typename Value, typename HashKey >
308  inline
309  Value ImageContainerByHashTree<Domain, Value, HashKey >::operator() ( const HashKey key ) const
310  {
311  return get ( key );
312  }
313  template < typename Domain, typename Value, typename HashKey >
314  inline
315  Value ImageContainerByHashTree<Domain, Value, HashKey >::operator() ( const Point &aPoint ) const
316  {
317  return get ( aPoint );
318  }
319 
320  template < typename Domain, typename Value, typename HashKey >
321  inline
322  Value ImageContainerByHashTree<Domain, Value, HashKey >::get ( const HashKey key ) const
323  {
324 
325  HashKey iterKey = key;
326  // node above the requested node
327  while ( iterKey != 0 )
328  {
329  Node* n = getNode ( iterKey );
330  if ( n )
331  return n->getObject();
332  iterKey >>= dim;
333  }
334  //if the node is deeper than the one requested
335  return blendChildren ( key );
336  }
337 
338 
339  template < typename Domain, typename Value, typename HashKey >
340  inline
341  Value ImageContainerByHashTree<Domain, Value, HashKey >::reverseGet ( const HashKey key ) const
342  {
343 
344  HashKey iterKey = key;
345  // node above the requested node
346  HashKey limit = myDepthMask << 1;
347  while ( iterKey < limit )
348  {
349  Node* n = getNode ( iterKey );
350  if ( n )
351  return blendChildren ( key );
352  iterKey <<= dim;
353  }
354  iterKey = key;
355  while ( iterKey != 0 )
356  {
357  Node* n = getNode ( iterKey );
358  if ( n )
359  return n->getObject();
360  iterKey >>= dim;
361  }
362  return 0;
363  }
364 
365 
366  template < typename Domain, typename Value, typename HashKey>
367  inline
368  Value
369  ImageContainerByHashTree<Domain, Value, HashKey >::get ( const Point & aPoint ) const
370  {
371  return get ( getKey ( aPoint ) );
372  }
373 
374  //Deprecated
375  template < typename Domain, typename Value, typename HashKey >
376  inline
377  Value
378  ImageContainerByHashTree<Domain, Value, HashKey >::upwardGet ( const HashKey key ) const
379  {
380  //cerr << "ImageContainerByHashTree::upWardGet" << endl;
381  HashKey aKey = key;
382 
383  while ( aKey )
384  {
385  HashKey key2 = getIntermediateKey ( aKey );
386  Node* iter = myData[key2];
387 
388  while ( iter != 0 )
389  {
390  if ( iter->getKey() == aKey )
391  return iter->getObject();
392  iter = iter->getNext();
393  }
394  aKey >>= dim; // transorm the key to search in an upper level
395  }
396  }
397 
398  template < typename Domain, typename Value, typename HashKey >
399  inline
400  HashKey
401  ImageContainerByHashTree<Domain, Value, HashKey >::getKey ( const Point & aPoint ) const
402  {
403  HashKey result = 0;
404  Point currentPos = aPoint - myOrigin;
405 
406  myMorton.interleaveBits ( currentPos, result );
407  // by convention, the root node has the key 0..01
408  // it makes it easy to determine the depth of a node by it's key (looking
409  // at the position of the most significant bit that is equal to 1)
410  result |= myDepthMask;
411 
412  return result;
413  }
414 
415  template < typename Domain, typename Value, typename HashKey >
416  inline
417  HashKey
418  ImageContainerByHashTree<Domain, Value, HashKey >::getIntermediateKey ( HashKey key ) const
419  {
420  return ( key & myPreComputedIntermediateMask );
421  }
422 
423 
424  template < typename Domain, typename Value, typename HashKey >
425  inline
426  bool
427  ImageContainerByHashTree<Domain, Value, HashKey >::Iterator::next()
428  {
429  if ( myNode )
430  {
431  myNode = myNode->getNext();
432  if ( myNode )
433  {
434  return true;
435  }
436  else
437  {
438  do
439  {
440  myNode = myContainerData[++myCurrentCell];
441  if ( myCurrentCell >= myArraySize )
442  return false;
443  }
444  while ( !myNode );
445  return true;
446  }
447  }
448  return false;
449  }
450 
451  // ---------------------------------------------------------------------
452  //
453  // ---------------------------------------------------------------------
454 
455  template < typename Domain, typename Value, typename HashKey >
456  inline
457  bool
458  ImageContainerByHashTree<Domain, Value, HashKey >::removeNode ( HashKey key )
459  {
460  HashKey key2 = getIntermediateKey ( key );
461  Node* iter = myData[key2];
462  // if the node is the first in the list we have to modify the pointer stored in myData
463  if ( iter && ( iter->getKey() == key ) )
464  {
465  myData[key2] = iter->getNext();
466  delete iter;
467  return true;
468  }
469  while ( iter )
470  {
471  Node* next = iter->getNext();
472  if ( next )
473  {
474  if ( next->getKey() == key )
475  {
476  iter->setNext ( next->getNext() );
477  delete next;
478  return true;
479  }
480  }
481  iter = iter->getNext();
482  }
483  return false;
484  }
485 
486  template < typename Domain, typename Value, typename HashKey >
487  inline
488  void
489  ImageContainerByHashTree<Domain, Value, HashKey >::recursiveRemoveNode ( HashKey key, unsigned int nbRecursions )
490  {
491  if ( removeNode ( key ) )
492  return;
493  if ( --nbRecursions > 0 )
494  {
495  HashKey children[myN];
496  myMorton.childrenKeys ( key, children );
497  for ( unsigned int i = 0; i < myN; ++i )
498  {
499  recursiveRemoveNode ( children[i], nbRecursions );
500  }
501  }
502  }
503 
504 
505 
506  // ---------------------------------------------------------------------
507  //
508  // ---------------------------------------------------------------------
509 
510  template < typename Domain, typename Value, typename HashKey >
511  inline
512  void
513  ImageContainerByHashTree<Domain, Value, HashKey >::setDepth ( unsigned int depth )
514  {
515  myTreeDepth = depth;
516  mySpanSize = 1 << depth;
517  //precompute the mask
518  myDepthMask = static_cast<HashKey> ( 1 ) << dim * depth;
519  }
520 
521 
522  template < typename Domain, typename Value, typename HashKey >
523  inline
524  unsigned int
525  ImageContainerByHashTree<Domain, Value, HashKey >::getKeyDepth ( HashKey key ) const
526  {
527  for ( int i = ( sizeof ( HashKey ) << 3 ) - 1; i >= 0; --i )
528  if ( key & ( static_cast<HashKey> ( 1 ) << i ) )
529  {
530  return ( i ) / dim;
531  }
532  return 0;
533  }
534 
535 
536  template < typename Domain, typename Value, typename HashKey >
537  inline
538  int*
539  ImageContainerByHashTree<Domain, Value, HashKey >::getCoordinatesFromKey ( HashKey key ) const
540  {
541  //remove the first bit equal 1
542  for ( int i = ( sizeof ( HashKey ) << 3 ) - 1; i >= 0; --i )
543  {
544  if ( key & Bits::mask<HashKey> ( i ) )
545  {
546  key &= ~Bits::mask<HashKey> ( i );
547  break;
548  }
549  }
550  int* coordinates = new int[dim];
551  //deinterleave the bits
552  for ( unsigned int i = 0; i < dim; ++i )
553  {
554  coordinates[i] = 0;
555  for ( unsigned int bitPos = 0; bitPos < ( sizeof ( HashKey ) << 3 ) / dim; ++bitPos )
556  {
557  if ( key & Bits::mask ( bitPos*dim + i ) )
558  {
559  coordinates[i] |= Bits::mask<HashKey> ( bitPos );
560  }
561  }
562  }
563  return coordinates;
564  }
565 
566 
567  template < typename Domain, typename Value, typename HashKey >
568  inline
569  bool
570  ImageContainerByHashTree<Domain, Value, HashKey >::isKeyValid ( HashKey key ) const
571  {
572  if ( !key )
573  return false;
574  if ( getKeyDepth ( key ) > myTreeDepth )
575  return false;
576 
577  int i = ( sizeof ( HashKey ) << 3 ) - 1;
578  for ( ; i >= 0; --i )
579  if ( key & ( static_cast<HashKey> ( 1 ) << i ) )
580  break;
581 
582  if ( i % dim )
583  {
584  return false;
585  }
586 
587  return true;
588  }
589 
590 
591  // ---------------------------------------------------------------------
592  // Debug
593  // ---------------------------------------------------------------------
594  template <typename Domain, typename Value , typename HashKey >
595  inline
596  void
597  ImageContainerByHashTree<Domain, Value, HashKey >::printState ( ostream& out, bool displayKeys ) const
598  {
599  out << "ImageContainerByHashTree::printState" << endl;
600  out << "depth: " << myTreeDepth << " (" << Bits::bitString ( myDepthMask ) << ")" << endl;
601  out << "dim: " << dim << "myN: " << myN << endl;
602  printTree ( ROOT_KEY, out, displayKeys );
603  }
604 
605  template <typename Domain, typename Value, typename HashKey >
606  inline
607  void
608  ImageContainerByHashTree<Domain, Value, HashKey >::printTree ( HashKey key, ostream& out, bool displayKeys ) const
609  {
610  unsigned int level = getKeyDepth ( key );
611  for ( unsigned int i = 0; i < level; ++i )
612  out << " ";
613  Node* n = getNode ( key );
614  if ( n )
615  {
616  out << " < " << n->getObject() << " > ";
617  if ( displayKeys )
618  out << Bits::bitString ( key, 8 );
619  out << endl;
620  }
621  else
622  {
623  out << " < x > ";
624  if ( displayKeys )
625  out << Bits::bitString ( key, 8 );
626  out << endl;
627  }
628 
629  if ( level < myTreeDepth )
630  {
631  HashKey children[myN];
632  myMorton.childrenKeys ( key, children );
633  for ( unsigned int i = 0; i < myN; ++i )
634  printTree ( children[i], out, displayKeys );
635  }
636  }
637 
638  template <typename Domain, typename Value, typename HashKey >
639  inline
640  void
641  ImageContainerByHashTree<Domain, Value, HashKey >::printInternalState ( ostream& out, unsigned int nbBits ) const
642  {
643  out << "ImageContainerByHashTree::printInternalState ----------------------------------" << endl;
644  out << "| <template> dim = " << dim << " myN = " << myN << endl;
645  out << "| tree depth = " << myTreeDepth << " mask = " << Bits::bitString ( myDepthMask ) << endl;
646 
647  for ( unsigned int i = 0; i < ( 1 << myKeySize ); ++i )
648  {
649  out << "| " << Bits::bitString ( i, myKeySize ) << " [";
650  if ( myData[i] )
651  {
652  out << "-]->(";
653  if ( nbBits )
654  out << Bits::bitString ( myData[i]->getKey(), nbBits ) << ":";
655  out << myData[i]->getObject() << ")";
656  Node* iter = myData[i]->getNext();
657  while ( iter )
658  {
659  out << "->(";
660  if ( nbBits )
661  out << Bits::bitString ( myData[i]->getKey(), nbBits ) << ":";
662  out << iter->getObject() << ")";
663  iter = iter->getNext();
664  }
665  out << endl;
666  }
667  else
668  {
669  cout << "x]" << endl;
670  }
671  }
672 
673  out << "| image size: " << getSpanSize() << "^" << dim << " (" << std::pow ( getSpanSize(), dim ) *sizeof ( Value ) << " bytes)" << endl;
674  out << "| " << getNbNodes() << " nodes - Empty lists: " << getNbEmptyLists() << " (" << getNbEmptyLists() *sizeof ( Node* ) << " bytes)" << endl;
675  out << "| Average collisions: " << getAverageCollisions() << " - Max collisions " << getMaxCollisions() << endl;
676  out << "----------------------------------------------------------------" << endl;
677  }
678 
679 
680  template <typename Domain, typename Value, typename HashKey >
681  inline
682  void
683  ImageContainerByHashTree<Domain, Value, HashKey >::printInfo ( ostream& out ) const
684  {
685  unsigned int nbNodes = getNbNodes();
686  unsigned int totalSize = sizeof ( *this ) + ( 1 << myKeySize ) * sizeof ( Node* ) + nbNodes * sizeof ( Node );
687 
688  out << "[ImageContainerByHashTree]: Dimension=" << ( int ) dim << ", HashKey size="
689  << myKeySize << ", Depth=" << myTreeDepth << ", image size=" << getSpanSize()
690  << "^" << ( int ) dim << " (" << std::pow ( ( double ) getSpanSize(), ( double ) dim ) *sizeof ( Value )
691  << " bytes)" << ", " << nbNodes << " nodes" << ", Empty lists=" << getNbEmptyLists()
692  << " (" << getNbEmptyLists() *sizeof ( Node* ) << " bytes)" << ", Average collisions=" << getAverageCollisions()
693  << ", Max collisions " << getMaxCollisions()
694  << ", total memory usage=" << totalSize << " bytes" << endl;
695  }
696 
697 
698 
699  template <typename Domain, typename Value, typename HashKey >
700  inline
701  unsigned int
702  ImageContainerByHashTree<Domain, Value, HashKey >::getNbNodes ( unsigned int intermediateKey ) const
703  {
704  if ( !myData[intermediateKey] )
705  {
706  return 0;
707  }
708  else
709  {
710  unsigned int count = 1;
711  Node* n = myData[intermediateKey]->getNext();
712  while ( n )
713  {
714  ++count;
715  n = n->getNext();
716  }
717  return count;
718  }
719  }
720 
721 
722 
723  template <typename Domain, typename Value, typename HashKey >
724  inline
725  unsigned int
726  ImageContainerByHashTree<Domain, Value, HashKey >::getNbNodes() const
727  {
728  unsigned int count = 0;
729  unsigned int arraySize = 1 << myKeySize;
730  for ( unsigned int i = 0; i < arraySize; ++i )
731  {
732  count += getNbNodes ( i );
733  }
734  return count;
735  }
736 
737 
738  template <typename Domain, typename Value, typename HashKey >
739  inline
740  unsigned int
741  ImageContainerByHashTree<Domain, Value, HashKey >::getNbEmptyLists() const
742  {
743  unsigned int count = 0;
744  unsigned int arraySize = 1 << myKeySize;
745  for ( unsigned int i = 0; i < arraySize; ++i )
746  {
747  if ( !myData[i] )
748  count++;
749  }
750  return count;
751  }
752 
753 
754  template<typename Domain, typename Value, typename HashKey >
755  inline
756  double
757  ImageContainerByHashTree<Domain, Value, HashKey >::getAverageCollisions() const
758  {
759  double count = 0;
760  double nbLists = 0;
761  unsigned int arraySize = 1 << myKeySize;
762  for ( unsigned int i = 0; i < arraySize; ++i )
763  {
764  if ( myData[i] )
765  {
766  count += getNbNodes ( i ) - 1;
767  nbLists++;
768  }
769  }
770  if ( nbLists == 0 )
771  {
772  trace.error() << "ImageContainerByHashTree::getAverageCollision() - error" << endl
773  << "the container is empty !" << endl;
774  return 0;
775  }
776  return count / nbLists;
777  }
778 
779 
780 
781  template <typename Domain, typename Value, typename HashKey >
782  inline
783  unsigned int
784  ImageContainerByHashTree<Domain, Value, HashKey >::getMaxCollisions() const
785  {
786  unsigned int count = 0;
787  unsigned int arraySize = 1 << myKeySize;
788  for ( unsigned int i = 0; i < arraySize; ++i )
789  {
790  if ( myData[i] )
791  {
792  unsigned int collision = getNbNodes ( i ) - 1;
793  if ( collision > count )
794  {
795  count = collision;
796  }
797  }
798  }
799  return count;
800  }
801 
802  //------------------------------------------------------------------------------
803  template <typename Domain, typename Value, typename HashKey >
804  inline
805  std::string
806  ImageContainerByHashTree<Domain, Value, HashKey >::className() const
807  {
808  return "ImageContainerByHashTree";
809  }
810 
811  template <typename Domain, typename Value, typename HashKey >
812  Value
813  ImageContainerByHashTree<Domain, Value, HashKey >::blendChildren ( HashKey key ) const
814  {
815  Node* n = getNode ( key );
816  if ( n )
817  {
818  return n->getObject();
819  }
820  else
821  {
822  HashKey children[myN];
823  myMorton.childrenKeys ( key, children );
824  float result = 0;
825  for ( unsigned int i = 0; i < myN; ++i )
826  {
827  result += blendChildren ( children[i] );
828  }
829  return static_cast<Value> ( result / myN );
830  }
831  }
832 
833 
834  template <typename Domain, typename Value, typename HashKey >
835  bool
836  ImageContainerByHashTree<Domain, Value, HashKey >::checkIntegrity ( HashKey key, bool leafAbove ) const
837  {
838  trace.info() << "Checking key=" << key << endl;
839  if ( !isKeyValid ( key ) )
840  {
841  trace.error() << "checkIntegrity->invalid key " << Bits::bitString ( key );
842  trace.info() << endl;
843  ASSERT ( 1 == 0 );
844  }
845 
846  Node* n = getNode ( key );
847 
848  if ( ( n != 0 ) && ( leafAbove ) )
849  {
850  trace.error() << "ImageContainerByHashTree::checkIntegrity - error:" << endl
851  << "at key " << Bits::bitString ( key ) << endl
852  << "several leafs found" << endl;
853  return false;
854  }
855 
856  if ( getKeyDepth ( key ) >= myTreeDepth )
857  {
858  if ( leafAbove || n )
859  {
860  return true;
861  }
862  else
863  {
864  trace.error() << "ImageContainerByHashTree::checkIntegrity - error:" << endl
865  << "at key " << Bits::bitString ( key ) << endl
866  << "no leaf found" << endl;
867  return false;
868  }
869  }
870 
871  HashKey children[myN];
872  myMorton.childrenKeys ( key, children );
873  bool returnValue = true;
874  for ( unsigned int i = 0; i < myN; ++i )
875  returnValue &= checkIntegrity ( children[i], ( n || leafAbove ) );
876  return returnValue;
877  }
878 
879 
880 
881 
883  // Interface - public :
884 
889  template < typename Domain, typename Value, typename HashKey>
890  inline
891  void
892  ImageContainerByHashTree< Domain, Value, HashKey>::selfDisplay ( std::ostream & out )
893  {
894  printInfo ( out );
895  }
896 
897 } // namespace DGtal
898 // //
900 
901 
Generated on Wed Dec 19 2012 19:10:26 for DGtal by   doxygen 1.8.1.1