DGtal 1.4.2
Loading...
Searching...
No Matches
ImageContainerByHashTree.h
1
17#pragma once
18
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
341
349 Value upwardGet(const HashKey key) const ;
350
358 Value reverseGet(const HashKey key) const;
359
360
371 void setValue(const HashKey key, const Value object);
372
383 void setValue(const Point& aPoint, const Value object);
384
391 inline unsigned int getSpanSize() const
392 {
393 return mySpanSize;
394 }
395
400 inline unsigned int getDepth() const
401 {
402 return myTreeDepth;
403 }
404
413 bool isKeyValid(HashKey key) const;
414
422 bool checkIntegrity(HashKey key = ROOT_KEY, bool leafAbove = false) const;
423
424 int myDebugCounter; //debug
425
426 //stuff that might be moved out of the class for reusability
427 HashKey getKey(const Point & aPoint) const;
428
429 unsigned int getKeyDepth(HashKey key) const;
430
432
440 void printState(std::ostream& out, bool displayKeys = false) const;
441
450 void printTree(HashKey key, std::ostream& out, bool displayKeys) const;
451
460 void printInternalState(std::ostream& out, unsigned int nbBits = 0) const;
461
476 void printInfo(std::ostream& out) const;
477
481 unsigned int getNbEmptyLists() const;
482
487 double getAverageCollisions() const;
488
492 unsigned int getMaxCollisions() const;
493
500 unsigned int getNbNodes(unsigned int intermediateKey) const;
501
505 unsigned int getNbNodes()const;
506
507
508 // -------------------------------------------------------------
517 {
518 public:
519 Iterator(Node** data, unsigned int position, unsigned int arraySize)
520 {
521 myArraySize = arraySize;
523 myNode = data[0];
524 myCurrentCell = position;
525 while ((!myNode) && (myCurrentCell < myArraySize))
526 {
528 }
529 }
530 bool isAtEnd()const
531 {
532 return myCurrentCell >= myArraySize;
533 }
535 {
536 return myNode->getObject();
537 }
539 {
540 return next();
541 }
542 bool operator == (const Iterator& it)
543 {
544 if (isAtEnd() && it.isAtEnd())
545 return true;
546 else
547 return (myNode == it.myNode);
548 }
549 bool operator != (const Iterator& it)
550 {
551 if (isAtEnd() && it.isAtEnd())
552 return false;
553 else
554 return (myNode != it.myNode);
555 }
556 inline HashKey getKey() const
557 {
558 return myNode->getKey();
559 }
560 bool next();
561 protected:
563 unsigned int myCurrentCell;
564 unsigned int myArraySize;
566 };
567
572 {
573 return Iterator(myData, 0, myArraySize);
574 }
575
580 {
582 }
583
584 void selfDisplay(std::ostream & out) const;
585
586 bool isValid() const
587 {
588 return checkIntegrity();
589 }
590
591 // ------------- realization CDrawableWithBoard2D --------------------
592 private:
593
594
595 public:
600 //DrawableWithBoard2D* defaultStyle() const;
601
605 std::string className() const;
606
607 protected:
608
609 template <typename C>
610 void
611 recursiveDraw(HashKey key, const double p1[2], const double len, Board2D & board, const C& cmap) const;
612
613
614 // -------------------------------------------------------------
621 class Node
622 {
623 public:
624
631 Node(Value aValue, HashKey key)
632 {
633 myData = aValue;
634 myKey = key;
635 }
636
640 inline Node* getNext()
641 {
642 return myNext;
643 }
644
645
651 inline void setNext(Node* next)
652 {
653 myNext = next;
654 }
655
661 {
662 return myKey;
663 }
664
669 inline Value& getObject()
670 {
671 return myData;
672 }
673 ~Node() { }
674 protected:
678 };// -----------------------------------------------------------
679
680
688 inline HashKey getIntermediateKey(const HashKey key) const;
689
690
700 Node* addNode(const Value object, const HashKey key)
701 {
702 Node* n = getNode(key);
703 if (n)
704 {
705 n->getObject() = object;
706 //n->setObject(object);
707 return n;
708 }
709 n = new Node(object, key);
710 HashKey key2 = getIntermediateKey(key);
711 n->setNext(myData[key2]);
712 myData[key2] = n;
713 return n;
714 }
715
716 public:
724 inline Node* getNode(const HashKey key) const // very used !! // public because Display2DFactory !!!
725 {
726 Node* iter = myData[getIntermediateKey(key)];
727 while (iter != 0)
728 {
729 if (iter->getKey() == key)
730 return iter;
731 iter = iter->getNext();
732 }
733 return 0;
734 }
735 protected:
736
743
749 void recursiveRemoveNode(HashKey key, unsigned int nbRecursions);
750
751
758 void setDepth(unsigned int depth);
759
767
768
769 //----------------------- internal data --------------------------------
770 protected:
771
776
781
787 unsigned int myKeySize;
788
789 unsigned int myArraySize;
790
794 unsigned int myTreeDepth;
795
796 unsigned int mySpanSize;
797
798
799 // myN is number of children per node.
800 BOOST_STATIC_CONSTANT( unsigned int, myN = NbChildrenPerNode );
801
802
803 public:
804 Point myOrigin; // public because Display2DFactory !!!
805 protected:
806
812
813 public:
815 Morton<HashKey, Point> myMorton; // public because Display2DFactory !!!
816
817
818 };
819
826 template<typename TDomain, typename TValue, typename THashKey >
827 std::ostream&
828 operator<< ( std::ostream & out, const ImageContainerByHashTree<TDomain, TValue, THashKey> & object )
829 {
830 object.selfDisplay( out);
831 return out;
832 }
833
834
835}
836} // namespace DGtal
837
839// Includes inline functions.
840#include "DGtal/images/ImageContainerByHashTree.ih"
841
842// //
844
845#endif // !defined ImageContainerByHashTree_h
846
847#undef ImageContainerByHashTree_RECURSES
848#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,...
Built-in iterator on an HashTree. This iterator visits all node in the tree.
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)
Morton< HashKey, Point > myMorton
The morton code computer.
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)
Value upwardGet(const HashKey key) const
void recursiveRemoveNode(HashKey key, unsigned int nbRecursions)
ImageContainerByHashTree< TDomain, TValue, THashKey > Self
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
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
SetValueIterator< Self > OutputIterator
output iterator
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: The traits class for all models of Cinteger.
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)