DGtal 1.4.2
Loading...
Searching...
No Matches
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 //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///////////////////////////////////////////////////////////////////////////////