Loading [MathJax]/extensions/TeX/AMSsymbols.js
DGtal 2.0.0
ImageContainerByHashTree.h
1
16
17#pragma once
18
31
32#if defined(ImageContainerByHashTree_RECURSES)
33#error Recursive header files inclusion detected in ImageContainerByHashTree.h
34#else // defined(ImageContainerByHashTree_RECURSES)
36#define ImageContainerByHashTree_RECURSES
37
38#if !defined ImageContainerByHashTree_h
40#define ImageContainerByHashTree_h
41
43// Inclusions
44#include <iostream>
45#include "DGtal/base/Common.h"
46#include "DGtal/base/CLabel.h"
47#include "DGtal/base/ConstRangeAdapter.h"
48#include "DGtal/images/DefaultConstImageRange.h"
49#include "DGtal/images/DefaultImageRange.h"
50
51#include "DGtal/kernel/domains/CDomain.h"
52#include "DGtal/kernel/domains/HyperRectDomain.h"
53#include "DGtal/kernel/SpaceND.h"
54#include "DGtal/base/Bits.h"
55#include "DGtal/images/Morton.h"
56#include "DGtal/images/SetValueIterator.h"
57#include "DGtal/io/Color.h"
58#include "DGtal/base/ExpressionTemplates.h"
60
61namespace DGtal
62{
63 namespace experimental
64 {
66 // template class ImageContainerByHashTree
127 template < typename TDomain, typename TValue, typename THashKey = typename DGtal::uint64_t >
129 {
130
131 protected:
132 class Node;
133
134
135 public:
136
138
139 typedef THashKey HashKey;
140
143 typedef TDomain Domain;
144 typedef typename Domain::Point Point;
145 typedef typename Domain::Vector Vector;
146 typedef typename Domain::Integer Integer;
147 typedef typename Domain::Size Size;
148 typedef typename Domain::Dimension Dimension;
149 typedef Point Vertex;
150
152 BOOST_STATIC_CONSTANT( Dimension, dimension = Domain::dimension);
153 BOOST_STATIC_CONSTANT( Dimension, dim = Domain::dimension);
155 BOOST_STATIC_CONSTANT( unsigned int, NbChildrenPerNode = PowHelper::VALUE);
156 BOOST_STATIC_CONSTANT( HashKey, ROOT_KEY = static_cast<THashKey>(1));
157
159 //(since constructed from two points as a bounding box)
160 BOOST_STATIC_ASSERT ((boost::is_same< Domain,
162
165 typedef TValue Value;
166 //typedef ConstRangeAdapter<typename Domain::ConstIterator, Self, Value > ConstRange;
169
172
173
174
192 ImageContainerByHashTree(const unsigned int hashKeySize,
193 const unsigned int depth,
194 const Value defaultValue);
195
214 ImageContainerByHashTree(const unsigned int hashKeySize,
215 const Point & p1,
216 const Point & p2,
217 const Value defaultValue);
218
236 const unsigned int hashKeySize = 3,
237 const Value defaultValue= NumberTraits<Value>::ZERO);
238
239
240 // TODO
241 // /*
242 // * Copy contructor.
243 // *
244 // * @param other object to copy.
245 // */
246 // ImageContainerByHashTree(const ImageContainerByHashTree<Domain, Value>& other);
247
248 // /*
249 // * Assignment.
250 // *
251 // * @param other object to copy.
252 // */
253 // ImageContainerByHashTree(const ImageContainerByHashTree<Domain, Value>& other);
254
255 // /*
256 // * Destructor
257 // * Free the memory allocated by @a myData
258 // */
259 // ~ImageContainerByHashTree();
260
261
265 const Domain &domain() const;
266
272
278
283 const Self & container() const { return *this; };
288 Self & container() { return *this; };
289
294 const Node** & data() const noexcept { return myData; };
299 Node** & data() noexcept { return myData; };
300
315 Value get(const HashKey key) const;
316
317
324 Value operator () (const HashKey key) const;
325
333
339 Value get(const Point & aPoint) const;
340
348 Value reverseGet(const HashKey key) const;
349
350
361 void setValue(const HashKey key, const Value object);
362
373 void setValue(const Point& aPoint, const Value object);
374
381 inline unsigned int getSpanSize() const
382 {
383 return mySpanSize;
384 }
385
390 inline unsigned int getDepth() const
391 {
392 return myTreeDepth;
393 }
394
403 bool isKeyValid(HashKey key) const;
404
412 bool checkIntegrity(HashKey key = ROOT_KEY, bool leafAbove = false) const;
413
414 int myDebugCounter; //debug
415
416 //stuff that might be moved out of the class for reusability
417 HashKey getKey(const Point & aPoint) const;
418
419 unsigned int getKeyDepth(HashKey key) const;
420
422
430 void printState(std::ostream& out, bool displayKeys = false) const;
431
440 void printTree(HashKey key, std::ostream& out, bool displayKeys) const;
441
450 void printInternalState(std::ostream& out, unsigned int nbBits = 0) const;
451
466 void printInfo(std::ostream& out) const;
467
471 unsigned int getNbEmptyLists() const;
472
477 double getAverageCollisions() const;
478
482 unsigned int getMaxCollisions() const;
483
490 unsigned int getNbNodes(unsigned int intermediateKey) const;
491
495 unsigned int getNbNodes()const;
496
497
498 // -------------------------------------------------------------
507 {
508 public:
509 Iterator(Node** data, unsigned int position, unsigned int arraySize)
510 {
511 myArraySize = arraySize;
513 myNode = data[0];
514 myCurrentCell = position;
515 while ((!myNode) && (myCurrentCell < myArraySize))
516 {
518 }
519 }
520 bool isAtEnd()const
521 {
522 return myCurrentCell >= myArraySize;
523 }
525 {
526 return myNode->getObject();
527 }
529 {
530 return next();
531 }
532 bool operator == (const Iterator& it)
533 {
534 if (isAtEnd() && it.isAtEnd())
535 return true;
536 else
537 return (myNode == it.myNode);
538 }
539 bool operator != (const Iterator& it)
540 {
541 if (isAtEnd() && it.isAtEnd())
542 return false;
543 else
544 return (myNode != it.myNode);
545 }
546 inline HashKey getKey() const
547 {
548 return myNode->getKey();
549 }
550 bool next();
551 protected:
553 unsigned int myCurrentCell;
554 unsigned int myArraySize;
556 };
557
561 Iterator begin()
562 {
563 return Iterator(myData, 0, myArraySize);
564 }
565
569 Iterator end()
570 {
571 return Iterator(myData, myArraySize, myArraySize);
572 }
573
574 void selfDisplay(std::ostream & out) const;
575
576 bool isValid() const
577 {
578 return checkIntegrity();
579 }
580
581 // ------------- realization CDrawableWithBoard2D --------------------
582 private:
583
584
585 public:
590 //DrawableWithBoard2D* defaultStyle() const;
591
595 std::string className() const;
596
597 protected:
598
599 template <typename C>
600 void
601 recursiveDraw(HashKey key, const double p1[2], const double len, Board2D & board, const C& cmap) const;
602
603
604 // -------------------------------------------------------------
611 class Node
612 {
613 public:
614
621 Node(Value aValue, HashKey key)
622 {
623 myData = aValue;
624 myKey = key;
625 }
626
630 inline Node* getNext()
631 {
632 return myNext;
633 }
634
635
641 inline void setNext(Node* next)
642 {
643 myNext = next;
644 }
645
651 {
652 return myKey;
653 }
654
659 inline Value& getObject()
660 {
661 return myData;
662 }
663 ~Node() { }
664 protected:
668 };// -----------------------------------------------------------
669
670
678 inline HashKey getIntermediateKey(const HashKey key) const;
679
680
690 Node* addNode(const Value object, const HashKey key)
691 {
692 Node* n = getNode(key);
693 if (n)
694 {
695 n->getObject() = object;
696 //n->setObject(object);
697 return n;
698 }
699 n = new Node(object, key);
700 HashKey key2 = getIntermediateKey(key);
701 n->setNext(myData[key2]);
702 myData[key2] = n;
703 return n;
704 }
705
706 public:
714 inline Node* getNode(const HashKey key) const // very used !! // public because Display2DFactory !!!
715 {
716 Node* iter = myData[getIntermediateKey(key)];
717 while (iter != 0)
718 {
719 if (iter->getKey() == key)
720 return iter;
721 iter = iter->getNext();
722 }
723 return 0;
724 }
725 protected:
726
733
739 void recursiveRemoveNode(HashKey key, unsigned int nbRecursions);
740
741
748 void setDepth(unsigned int depth);
749
757
758
759 //----------------------- internal data --------------------------------
760 protected:
761
766
770 Node** myData;
771
777 unsigned int myKeySize;
778
779 unsigned int myArraySize;
780
784 unsigned int myTreeDepth;
785
786 unsigned int mySpanSize;
787
788
789 // myN is number of children per node.
790 BOOST_STATIC_CONSTANT( unsigned int, myN = NbChildrenPerNode );
791
792
793 public:
794 Point myOrigin; // public because Display2DFactory !!!
795 protected:
796
802
803 public:
805 Morton<HashKey, Point> myMorton; // public because Display2DFactory !!!
806
807
808 };
809
816 template<typename TDomain, typename TValue, typename THashKey >
817 std::ostream&
818 operator<< ( std::ostream & out, const ImageContainerByHashTree<TDomain, TValue, THashKey> & object )
819 {
820 object.selfDisplay( out);
821 return out;
822 }
823
824
825}
826} // namespace DGtal
827
829// Includes inline functions.
830#include "DGtal/images/ImageContainerByHashTree.ih"
831
832// //
834
835#endif // !defined ImageContainerByHashTree_h
836
837#undef ImageContainerByHashTree_RECURSES
838#endif // else defined(ImageContainerByHashTree_RECURSES)
Aim: This class specializes a 'Board' class so as to display DGtal objects more naturally (with <<)....
Definition Board2D.h:71
Aim: model of CConstBidirectionalRangeFromPoint that adapts the domain of an image in order to iterat...
Aim: model of CConstBidirectionalRangeFromPoint and CBidirectionalRangeWithWritableIteratorFromPoint ...
Aim: Parallelepidec region of a digital space, model of a 'CDomain'.
Aim: Implements the binary Morton code construction in nD.
Definition Morton.h:78
Aim: implements an output iterator, which is able to write values in an underlying image,...
Iterator(Node **data, unsigned int position, unsigned int arraySize)
Model of CImageContainer implementing the association key<->Value using a hash tree....
bool checkIntegrity(HashKey key=ROOT_KEY, bool leafAbove=false) const
HashKey getKey(const Point &aPoint) const
Value get(const Point &aPoint) const
Node * addNode(const Value object, const HashKey key)
unsigned int getKeyDepth(HashKey key) const
Value reverseGet(const HashKey key) const
BOOST_STATIC_CONSTANT(Dimension, dimension=Domain::dimension)
static constants
ImageContainerByHashTree(const unsigned int hashKeySize, const Point &p1, const Point &p2, const Value defaultValue)
Value operator()(const Point &aPoint) const
void setValue(const Point &aPoint, const Value object)
ImageContainerByHashTree(const Domain &aDomain, const unsigned int hashKeySize=3, const Value defaultValue=NumberTraits< Value >::ZERO)
ImageContainerByHashTree(const unsigned int hashKeySize, const unsigned int depth, const Value defaultValue)
HashKey getIntermediateKey(const HashKey key) const
BOOST_STATIC_CONSTANT(Dimension, dim=Domain::dimension)
BOOST_CONCEPT_ASSERT((concepts::CDomain< TDomain >))
domain
BOOST_STATIC_CONSTANT(unsigned int, myN=NbChildrenPerNode)
void recursiveDraw(HashKey key, const double p1[2], const double len, Board2D &board, const C &cmap) const
void printInfo(std::ostream &out) const
BOOST_STATIC_CONSTANT(HashKey, ROOT_KEY=static_cast< THashKey >(1))
void selfDisplay(std::ostream &out) const
BOOST_CONCEPT_ASSERT((concepts::CLabel< TValue >))
values range
Value operator()(const HashKey key) const
Value get(const HashKey key) const
BOOST_STATIC_CONSTANT(unsigned int, NbChildrenPerNode=PowHelper::VALUE)
void recursiveRemoveNode(HashKey key, unsigned int nbRecursions)
BOOST_STATIC_ASSERT((boost::is_same< Domain, HyperRectDomain< typename Domain::Space > >::value))
domain should be rectangular
void printInternalState(std::ostream &out, unsigned int nbBits=0) const
void printState(std::ostream &out, bool displayKeys=false) const
ImageContainerByHashTree< TDomain, TValue, THashKey > Self
void printTree(HashKey key, std::ostream &out, bool displayKeys) const
void setValue(const HashKey key, const Value object)
int * getCoordinatesFromKey(HashKey key) const
unsigned int getNbNodes(unsigned int intermediateKey) const
Experimental functions and types of the DGtal library.
std::ostream & operator<<(std::ostream &out, const ImageContainerByHashTree< TDomain, TValue, THashKey > &object)
DGtal is the top-level namespace which contains all DGtal functions and types.
Aim: This concept represents a digital domain, i.e. a non mutable subset of points of the given digit...
Definition CDomain.h:130
Aim: Define the concept of DGtal labels. Models of CLabel can be default-constructible,...
Definition CLabel.h:93
const Point aPoint(3, 4)