DGtal  0.9.2
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)
35 
36 #define ImageContainerByHashTree_RECURSES
37 
38 #if !defined ImageContainerByHashTree_h
39 
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 
235  ImageContainerByHashTree(const Domain &aDomain,
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 
271  ConstRange constRange() const;
272 
277  Range range() ;
278 
279 
294  Value get(const HashKey key) const;
295 
296 
303  Value operator () (const HashKey key) const;
304 
311  Value operator()(const Point &aPoint) const;
312 
318  Value get(const Point & aPoint) const;
319 
320 
328  Value upwardGet(const HashKey key) const ;
329 
337  Value reverseGet(const HashKey key) const;
338 
339 
350  void setValue(const HashKey key, const Value object);
351 
362  void setValue(const Point& aPoint, const Value object);
363 
370  inline unsigned int getSpanSize() const
371  {
372  return mySpanSize;
373  }
374 
379  inline unsigned int getDepth() const
380  {
381  return myTreeDepth;
382  }
383 
392  bool isKeyValid(HashKey key) const;
393 
401  bool checkIntegrity(HashKey key = ROOT_KEY, bool leafAbove = false) const;
402 
403  int myDebugCounter; //debug
404 
405  //stuff that might be moved out of the class for reusability
406  HashKey getKey(const Point & aPoint) const;
407 
408  unsigned int getKeyDepth(HashKey key) const;
409 
410  int* getCoordinatesFromKey(HashKey key) const;
411 
419  void printState(std::ostream& out, bool displayKeys = false) const;
420 
429  void printTree(HashKey key, std::ostream& out, bool displayKeys) const;
430 
439  void printInternalState(std::ostream& out, unsigned int nbBits = 0) const;
440 
455  void printInfo(std::ostream& out) const;
456 
460  unsigned int getNbEmptyLists() const;
461 
466  double getAverageCollisions() const;
467 
471  unsigned int getMaxCollisions() const;
472 
479  unsigned int getNbNodes(unsigned int intermediateKey) const;
480 
484  unsigned int getNbNodes()const;
485 
486 
487  // -------------------------------------------------------------
495  class Iterator
496  {
497  public:
498  Iterator(Node** data, unsigned int position, unsigned int arraySize)
499  {
500  myArraySize = arraySize;
501  myContainerData = data;
502  myNode = data[0];
503  myCurrentCell = position;
504  while ((!myNode) && (myCurrentCell < myArraySize))
505  {
507  }
508  }
509  bool isAtEnd()const
510  {
511  return myCurrentCell >= myArraySize;
512  }
513  Value& operator*()
514  {
515  return myNode->getObject();
516  }
518  {
519  return next();
520  }
521  bool operator == (const Iterator& it)
522  {
523  if (isAtEnd() && it.isAtEnd())
524  return true;
525  else
526  return (myNode == it.myNode);
527  }
528  bool operator != (const Iterator& it)
529  {
530  if (isAtEnd() && it.isAtEnd())
531  return false;
532  else
533  return (myNode != it.myNode);
534  }
535  inline HashKey getKey() const
536  {
537  return myNode->getKey();
538  }
539  bool next();
540  protected:
542  unsigned int myCurrentCell;
543  unsigned int myArraySize;
545  };
546 
551  {
552  return Iterator(myData, 0, myArraySize);
553  }
554 
559  {
561  }
562 
563  void selfDisplay(std::ostream & out) const;
564 
565  bool isValid() const
566  {
567  return checkIntegrity();
568  }
569 
570  // ------------- realization CDrawableWithBoard2D --------------------
571  private:
572 
573 
574  public:
579  //DrawableWithBoard2D* defaultStyle() const;
580 
584  std::string className() const;
585 
586  protected:
587 
588  template <typename C>
589  void
590  recursiveDraw(HashKey key, const double p1[2], const double len, Board2D & board, const C& cmap) const;
591 
592 
593  // -------------------------------------------------------------
600  class Node
601  {
602  public:
603 
610  Node(Value aValue, HashKey key)
611  {
612  myData = aValue;
613  myKey = key;
614  }
615 
619  inline Node* getNext()
620  {
621  return myNext;
622  }
623 
624 
630  inline void setNext(Node* next)
631  {
632  myNext = next;
633  }
634 
639  inline HashKey getKey()
640  {
641  return myKey;
642  }
643 
648  inline Value& getObject()
649  {
650  return myData;
651  }
652  ~Node() { }
653  protected:
654  HashKey myKey;
656  Value myData;
657  };// -----------------------------------------------------------
658 
659 
667  inline HashKey getIntermediateKey(const HashKey key) const;
668 
669 
679  Node* addNode(const Value object, const HashKey key)
680  {
681  Node* n = getNode(key);
682  if (n)
683  {
684  n->getObject() = object;
685  //n->setObject(object);
686  return n;
687  }
688  n = new Node(object, key);
689  HashKey key2 = getIntermediateKey(key);
690  n->setNext(myData[key2]);
691  myData[key2] = n;
692  return n;
693  }
694 
695  public:
703  inline Node* getNode(const HashKey key) const // very used !! // public because Display2DFactory !!!
704  {
705  Node* iter = myData[getIntermediateKey(key)];
706  while (iter != 0)
707  {
708  if (iter->getKey() == key)
709  return iter;
710  iter = iter->getNext();
711  }
712  return 0;
713  }
714  protected:
715 
721  bool removeNode(HashKey key);
722 
728  void recursiveRemoveNode(HashKey key, unsigned int nbRecursions);
729 
730 
737  void setDepth(unsigned int depth);
738 
745  Value blendChildren(HashKey key) const;
746 
747 
748  //----------------------- internal data --------------------------------
749  protected:
750 
754  Domain myDomain;
755 
760 
766  unsigned int myKeySize;
767 
768  unsigned int myArraySize;
769 
773  unsigned int myTreeDepth;
774 
775  unsigned int mySpanSize;
776 
777 
778  // myN is number of children per node.
779  BOOST_STATIC_CONSTANT( unsigned int, myN = NbChildrenPerNode );
780 
781 
782  public:
783  Point myOrigin; // public because Display2DFactory !!!
784  protected:
785 
789  HashKey myDepthMask;
790  HashKey myPreComputedIntermediateMask; // ~((~0) << _keySize)
791 
792  public:
794  Morton<HashKey, Point> myMorton; // public because Display2DFactory !!!
795 
796 
797  };
798 
805  template<typename TDomain, typename TValue, typename THashKey >
806  std::ostream&
807  operator<< ( std::ostream & out, const ImageContainerByHashTree<TDomain, TValue, THashKey> & object )
808  {
809  object.selfDisplay( out);
810  return out;
811  }
812 
813 
814 }
815 } // namespace DGtal
816 
818 // Includes inline functions.
819 #include "DGtal/images/ImageContainerByHashTree.ih"
820 
821 // //
823 
824 #endif // !defined ImageContainerByHashTree_h
825 
826 #undef ImageContainerByHashTree_RECURSES
827 #endif // else defined(ImageContainerByHashTree_RECURSES)
void printInternalState(std::ostream &out, unsigned int nbBits=0) const
BOOST_CONCEPT_ASSERT((concepts::CDomain< TDomain >))
domain
void printState(std::ostream &out, bool displayKeys=false) const
BOOST_STATIC_ASSERT((boost::is_same< Domain, HyperRectDomain< typename Domain::Space > >::value))
domain should be rectangular
Aim: model of CConstBidirectionalRangeFromPoint that adapts the domain of an image in order to iterat...
Aim: Define the concept of DGtal labels. Models of CLabel can be default-constructible, assignable and equality comparable.
Definition: CLabel.h:91
HashKey getKey(const Point &aPoint) const
Aim: model of CConstBidirectionalRangeFromPoint and CBidirectionalRangeWithWritableIteratorFromPoint ...
Aim: implements an output iterator, which is able to write values in an underlying image...
void recursiveRemoveNode(HashKey key, unsigned int nbRecursions)
Node * addNode(const Value object, const HashKey key)
Value reverseGet(const HashKey key) const
void selfDisplay(std::ostream &out) const
Aim: Parallelepidec region of a digital space, model of a 'CDomain'.
ImageContainerByHashTree(const unsigned int hashKeySize, const unsigned int depth, const Value defaultValue)
bool checkIntegrity(HashKey key=ROOT_KEY, bool leafAbove=false) const
unsigned int getKeyDepth(HashKey key) const
HashKey getIntermediateKey(const HashKey key) const
Iterator(Node **data, unsigned int position, unsigned int arraySize)
Aim: This concept represents a digital domain, i.e. a non mutable subset of points of the given digit...
Definition: CDomain.h:129
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:69
void recursiveDraw(HashKey key, const double p1[2], const double len, Board2D &board, const C &cmap) const
Value operator()(const HashKey key) const
int * getCoordinatesFromKey(HashKey key) const
SetValueIterator< Self > OutputIterator
output iterator
Model of CImageContainer implementing the association key<->Value using a hash tree. This class provides a built-in iterator.
DGtal is the top-level namespace which contains all DGtal functions and types.
void printInfo(std::ostream &out) const
ImageContainerByHashTree< TDomain, TValue, THashKey > Self
Aim: Implements the binary Morton code construction in nD.
Definition: Morton.h:77
void printTree(HashKey key, std::ostream &out, bool displayKeys) const
void setValue(const HashKey key, const Value object)
Value upwardGet(const HashKey key) const
Built-in iterator on an HashTree. This iterator visits all node in the tree.
Morton< HashKey, Point > myMorton
The morton code computer.
BOOST_STATIC_CONSTANT(Dimension, dimension=Domain::dimension)
static constants
Aim: This class specializes a 'Board' class so as to display DGtal objects more naturally (with <<)...
Definition: Board2D.h:70