DGtal  1.5.beta
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 
61 namespace 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 
332  Value operator()(const Point &aPoint) const;
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  // -------------------------------------------------------------
516  class Iterator
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 
660  inline HashKey getKey()
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 
742  bool removeNode(HashKey key);
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 
811  HashKey myPreComputedIntermediateMask; // ~((~0) << _keySize)
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
int * getCoordinatesFromKey(HashKey key) const
Value get(const Point &aPoint) const
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
Node * addNode(const Value object, const HashKey key)
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)
SetValueIterator< Self > OutputIterator
output iterator
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)
unsigned int getNbNodes(unsigned int intermediateKey) const
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.
Definition: NumberTraits.h:564
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)
unsigned int dim(const Vector &z)