Loading [MathJax]/extensions/TeX/AMSsymbols.js
DGtal 2.0.0
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 ------------------------------
51namespace 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 template < typename Domain, typename Value, typename HashKey >
383 inline
384 HashKey
385 ImageContainerByHashTree<Domain, Value, HashKey >::getKey ( const Point & aPoint ) const
386 {
387 HashKey result = 0;
388 Point currentPos = aPoint - myOrigin;
389
390 myMorton.interleaveBits ( currentPos, result );
391 // by convention, the root node has the key 0..01
392 // it makes it easy to determine the depth of a node by it's key (looking
393 // at the position of the most significant bit that is equal to 1)
394 result |= myDepthMask;
395
396 return result;
397 }
398
399 template < typename Domain, typename Value, typename HashKey >
400 inline
401 HashKey
402 ImageContainerByHashTree<Domain, Value, HashKey >::getIntermediateKey ( HashKey key ) const
403 {
404 return ( key & myPreComputedIntermediateMask );
405 }
406
407
408 template < typename Domain, typename Value, typename HashKey >
409 inline
410 bool
411 ImageContainerByHashTree<Domain, Value, HashKey >::Iterator::next()
412 {
413 if ( myNode )
414 {
415 myNode = myNode->getNext();
416 if ( myNode )
417 {
418 return true;
419 }
420 else
421 {
422 do
423 {
424 myNode = myContainerData[++myCurrentCell];
425 if ( myCurrentCell >= myArraySize )
426 return false;
427 }
428 while ( !myNode );
429 return true;
430 }
431 }
432 return false;
433 }
434
435 // ---------------------------------------------------------------------
436 //
437 // ---------------------------------------------------------------------
438
439 template < typename Domain, typename Value, typename HashKey >
440 inline
441 bool
442 ImageContainerByHashTree<Domain, Value, HashKey >::removeNode ( HashKey key )
443 {
444 HashKey key2 = getIntermediateKey ( key );
445 Node* iter = myData[key2];
446 // if the node is the first in the list we have to modify the pointer stored in myData
447 if ( iter && ( iter->getKey() == key ) )
448 {
449 myData[key2] = iter->getNext();
450 delete iter;
451 return true;
452 }
453 while ( iter )
454 {
455 Node* next = iter->getNext();
456 if ( next )
457 {
458 if ( next->getKey() == key )
459 {
460 iter->setNext ( next->getNext() );
461 delete next;
462 return true;
463 }
464 }
465 iter = iter->getNext();
466 }
467 return false;
468 }
469
470 template < typename Domain, typename Value, typename HashKey >
471 inline
472 void
473 ImageContainerByHashTree<Domain, Value, HashKey >::recursiveRemoveNode ( HashKey key, unsigned int nbRecursions )
474 {
475 if ( removeNode ( key ) )
476 return;
477 if ( --nbRecursions > 0 )
478 {
479 HashKey children[myN];
480 myMorton.childrenKeys ( key, children );
481 for ( unsigned int i = 0; i < myN; ++i )
482 {
483 recursiveRemoveNode ( children[i], nbRecursions );
484 }
485 }
486 }
487
488
489
490 // ---------------------------------------------------------------------
491 //
492 // ---------------------------------------------------------------------
493
494 template < typename Domain, typename Value, typename HashKey >
495 inline
496 void
497 ImageContainerByHashTree<Domain, Value, HashKey >::setDepth ( unsigned int depth )
498 {
499 myTreeDepth = depth;
500 mySpanSize = 1 << depth;
501 //precompute the mask
502 myDepthMask = static_cast<HashKey> ( 1 ) << dim * depth;
503 }
504
505
506 template < typename Domain, typename Value, typename HashKey >
507 inline
508 unsigned int
509 ImageContainerByHashTree<Domain, Value, HashKey >::getKeyDepth ( HashKey key ) const
510 {
511 for ( int i = ( sizeof ( HashKey ) << 3 ) - 1; i >= 0; --i )
512 if ( key & ( static_cast<HashKey> ( 1 ) << i ) )
513 {
514 return ( i ) / dim;
515 }
516 return 0;
517 }
518
519
520 template < typename Domain, typename Value, typename HashKey >
521 inline
522 int*
523 ImageContainerByHashTree<Domain, Value, HashKey >::getCoordinatesFromKey ( HashKey key ) const
524 {
525 //remove the first bit equal 1
526 for ( int i = ( sizeof ( HashKey ) << 3 ) - 1; i >= 0; --i )
527 {
528 if ( key & Bits::mask<HashKey> ( i ) )
529 {
530 key &= ~Bits::mask<HashKey> ( i );
531 break;
532 }
533 }
534 int* coordinates = new int[dim];
535 //deinterleave the bits
536 for ( unsigned int i = 0; i < dim; ++i )
537 {
538 coordinates[i] = 0;
539 for ( unsigned int bitPos = 0; bitPos < ( sizeof ( HashKey ) << 3 ) / dim; ++bitPos )
540 {
541 if ( key & Bits::mask ( bitPos*dim + i ) )
542 {
543 coordinates[i] |= Bits::mask<HashKey> ( bitPos );
544 }
545 }
546 }
547 return coordinates;
548 }
549
550
551 template < typename Domain, typename Value, typename HashKey >
552 inline
553 bool
554 ImageContainerByHashTree<Domain, Value, HashKey >::isKeyValid ( HashKey key ) const
555 {
556 if ( !key )
557 return false;
558 if ( getKeyDepth ( key ) > myTreeDepth )
559 return false;
560
561 int i = ( sizeof ( HashKey ) << 3 ) - 1;
562 for ( ; i >= 0; --i )
563 if ( key & ( static_cast<HashKey> ( 1 ) << i ) )
564 break;
565
566 if ( i % dim )
567 {
568 return false;
569 }
570
571 return true;
572 }
573
574
575 // ---------------------------------------------------------------------
576 // Debug
577 // ---------------------------------------------------------------------
578 template <typename Domain, typename Value , typename HashKey >
579 inline
580 void
581 ImageContainerByHashTree<Domain, Value, HashKey >::printState ( std::ostream& out, bool displayKeys ) const
582 {
583 out << "ImageContainerByHashTree::printState" << std::endl;
584 out << "depth: " << myTreeDepth << " (" << Bits::bitString ( myDepthMask ) << ")" << std::endl;
585 out << "dim: " << dim << "myN: " << myN << std::endl;
586 printTree ( ROOT_KEY, out, displayKeys );
587 }
588
589 template <typename Domain, typename Value, typename HashKey >
590 inline
591 void
592 ImageContainerByHashTree<Domain, Value, HashKey >::printTree ( HashKey key, std::ostream& out, bool displayKeys ) const
593 {
594 unsigned int level = getKeyDepth ( key );
595 for ( unsigned int i = 0; i < level; ++i )
596 out << " ";
597 Node* n = getNode ( key );
598 if ( n )
599 {
600 out << " < " << n->getObject() << " > ";
601 if ( displayKeys )
602 out << Bits::bitString ( key, 8 );
603 out << std::endl;
604 }
605 else
606 {
607 out << " < x > ";
608 if ( displayKeys )
609 out << Bits::bitString ( key, 8 );
610 out << std::endl;
611 }
612
613 if ( level < myTreeDepth )
614 {
615 HashKey children[myN];
616 myMorton.childrenKeys ( key, children );
617 for ( unsigned int i = 0; i < myN; ++i )
618 printTree ( children[i], out, displayKeys );
619 }
620 }
621
622 template <typename Domain, typename Value, typename HashKey >
623 inline
624 void
625 ImageContainerByHashTree<Domain, Value, HashKey >::printInternalState ( std::ostream& out, unsigned int nbBits ) const
626 {
627 out << "ImageContainerByHashTree::printInternalState ----------------------------------" << std::endl;
628 out << "| <template> dim = " << dim << " myN = " << myN << std::endl;
629 out << "| tree depth = " << myTreeDepth << " mask = " << Bits::bitString ( myDepthMask ) << std::endl;
630
631 for ( unsigned int i = 0; i < ( 1 << myKeySize ); ++i )
632 {
633 out << "| " << Bits::bitString ( i, myKeySize ) << " [";
634 if ( myData[i] )
635 {
636 out << "-]->(";
637 if ( nbBits )
638 out << Bits::bitString ( myData[i]->getKey(), nbBits ) << ":";
639 out << myData[i]->getObject() << ")";
640 Node* iter = myData[i]->getNext();
641 while ( iter )
642 {
643 out << "->(";
644 if ( nbBits )
645 out << Bits::bitString ( myData[i]->getKey(), nbBits ) << ":";
646 out << iter->getObject() << ")";
647 iter = iter->getNext();
648 }
649 out << std::endl;
650 }
651 else
652 {
653 std::cout << "x]" << std::endl;
654 }
655 }
656
657 out << "| image size: " << getSpanSize() << "^" << dim << " (" << std::pow ( getSpanSize(), dim ) *sizeof ( Value ) << " bytes)" << std::endl;
658 out << "| " << getNbNodes() << " nodes - Empty lists: " << getNbEmptyLists() << " (" << getNbEmptyLists() *sizeof ( Node* ) << " bytes)" << std::endl;
659 out << "| Average collisions: " << getAverageCollisions() << " - Max collisions " << getMaxCollisions() << std::endl;
660 out << "----------------------------------------------------------------" << std::endl;
661 }
662
663
664 template <typename Domain, typename Value, typename HashKey >
665 inline
666 void
667 ImageContainerByHashTree<Domain, Value, HashKey >::printInfo ( std::ostream& out ) const
668 {
669 unsigned int nbNodes = getNbNodes();
670 unsigned int totalSize = sizeof ( *this ) + ( 1 << myKeySize ) * sizeof ( Node* ) + nbNodes * sizeof ( Node );
671
672 out << "[ImageContainerByHashTree]: Dimension=" << ( int ) dim << ", HashKey size="
673 << myKeySize << ", Depth=" << myTreeDepth << ", image size=" << getSpanSize()
674 << "^" << ( int ) dim << " (" << std::pow ( ( double ) getSpanSize(), ( double ) dim ) *sizeof ( Value )
675 << " bytes)" << ", " << nbNodes << " nodes" << ", Empty lists=" << getNbEmptyLists()
676 << " (" << getNbEmptyLists() *sizeof ( Node* ) << " bytes)" << ", Average collisions=" << getAverageCollisions()
677 << ", Max collisions " << getMaxCollisions()
678 << ", total memory usage=" << totalSize << " bytes" << std::endl;
679 }
680
681
682
683 template <typename Domain, typename Value, typename HashKey >
684 inline
685 unsigned int
686 ImageContainerByHashTree<Domain, Value, HashKey >::getNbNodes ( unsigned int intermediateKey ) const
687 {
688 if ( !myData[intermediateKey] )
689 {
690 return 0;
691 }
692 else
693 {
694 unsigned int count = 1;
695 Node* n = myData[intermediateKey]->getNext();
696 while ( n )
697 {
698 ++count;
699 n = n->getNext();
700 }
701 return count;
702 }
703 }
704
705
706
707 template <typename Domain, typename Value, typename HashKey >
708 inline
709 unsigned int
710 ImageContainerByHashTree<Domain, Value, HashKey >::getNbNodes() const
711 {
712 unsigned int count = 0;
713 unsigned int arraySize = 1 << myKeySize;
714 for ( unsigned int i = 0; i < arraySize; ++i )
715 {
716 count += getNbNodes ( i );
717 }
718 return count;
719 }
720
721
722 template <typename Domain, typename Value, typename HashKey >
723 inline
724 unsigned int
725 ImageContainerByHashTree<Domain, Value, HashKey >::getNbEmptyLists() const
726 {
727 unsigned int count = 0;
728 unsigned int arraySize = 1 << myKeySize;
729 for ( unsigned int i = 0; i < arraySize; ++i )
730 {
731 if ( !myData[i] )
732 count++;
733 }
734 return count;
735 }
736
737
738 template<typename Domain, typename Value, typename HashKey >
739 inline
740 double
741 ImageContainerByHashTree<Domain, Value, HashKey >::getAverageCollisions() const
742 {
743 double count = 0;
744 double nbLists = 0;
745 unsigned int arraySize = 1 << myKeySize;
746 for ( unsigned int i = 0; i < arraySize; ++i )
747 {
748 if ( myData[i] )
749 {
750 count += getNbNodes ( i ) - 1;
751 nbLists++;
752 }
753 }
754 if ( nbLists == 0 )
755 {
756 trace.error() << "ImageContainerByHashTree::getAverageCollision() - error" << std::endl
757 << "the container is empty !" << std::endl;
758 return 0;
759 }
760 return count / nbLists;
761 }
762
763
764
765 template <typename Domain, typename Value, typename HashKey >
766 inline
767 unsigned int
768 ImageContainerByHashTree<Domain, Value, HashKey >::getMaxCollisions() const
769 {
770 unsigned int count = 0;
771 unsigned int arraySize = 1 << myKeySize;
772 for ( unsigned int i = 0; i < arraySize; ++i )
773 {
774 if ( myData[i] )
775 {
776 unsigned int collision = getNbNodes ( i ) - 1;
777 if ( collision > count )
778 {
779 count = collision;
780 }
781 }
782 }
783 return count;
784 }
785
786 //------------------------------------------------------------------------------
787 template <typename Domain, typename Value, typename HashKey >
788 inline
789 std::string
790 ImageContainerByHashTree<Domain, Value, HashKey >::className() const
791 {
792 return "ImageContainerByHashTree";
793 }
794
795 template <typename Domain, typename Value, typename HashKey >
796 Value
797 ImageContainerByHashTree<Domain, Value, HashKey >::blendChildren ( HashKey key ) const
798 {
799 Node* n = getNode ( key );
800 if ( n )
801 {
802 return n->getObject();
803 }
804 else
805 {
806 HashKey children[myN];
807 myMorton.childrenKeys ( key, children );
808 float result = 0;
809 for ( unsigned int i = 0; i < myN; ++i )
810 {
811 result += blendChildren ( children[i] );
812 }
813 return static_cast<Value> ( result / myN );
814 }
815 }
816
817
818 template <typename Domain, typename Value, typename HashKey >
819 bool
820 ImageContainerByHashTree<Domain, Value, HashKey >::checkIntegrity ( HashKey key, bool leafAbove ) const
821 {
822 trace.info() << "Checking key=" << key << std::endl;
823 if ( !isKeyValid ( key ) )
824 {
825 trace.error() << "checkIntegrity->invalid key " << Bits::bitString ( key );
826 trace.info() << std::endl;
827 ASSERT ( 1 == 0 );
828 }
829
830 Node* n = getNode ( key );
831
832 if ( ( n != 0 ) && ( leafAbove ) )
833 {
834 trace.error() << "ImageContainerByHashTree::checkIntegrity - error:" << std::endl
835 << "at key " << Bits::bitString ( key ) << std::endl
836 << "several leafs found" << std::endl;
837 return false;
838 }
839
840 if ( getKeyDepth ( key ) >= myTreeDepth )
841 {
842 if ( leafAbove || n )
843 {
844 return true;
845 }
846 else
847 {
848 trace.error() << "ImageContainerByHashTree::checkIntegrity - error:" << std::endl
849 << "at key " << Bits::bitString ( key ) << std::endl
850 << "no leaf found" << std::endl;
851 return false;
852 }
853 }
854
855 HashKey children[myN];
856 myMorton.childrenKeys ( key, children );
857 bool returnValue = true;
858 for ( unsigned int i = 0; i < myN; ++i )
859 returnValue &= checkIntegrity ( children[i], ( n || leafAbove ) );
860 return returnValue;
861 }
862
863
864
865
866 ///////////////////////////////////////////////////////////////////////////////
867 // Interface - public :
868
869 /**
870 * Writes/Displays the object on an output stream.
871 * @param out the output stream where the object is written.
872 */
873 template < typename Domain, typename Value, typename HashKey>
874 inline
875 void
876 ImageContainerByHashTree< Domain, Value, HashKey>::selfDisplay ( std::ostream & out ) const
877 {
878 printInfo ( out );
879 }
880}
881} // namespace DGtal
882// //
883///////////////////////////////////////////////////////////////////////////////