ImageContainerByHashTree.h

 
#pragma once
 
#if defined(ImageContainerByHashTree_RECURSES)
#error Recursive header files inclusion detected in ImageContainerByHashTree.h
#else // defined(ImageContainerByHashTree_RECURSES)
 
#define ImageContainerByHashTree_RECURSES
 
#if !defined ImageContainerByHashTree_h
 
#define ImageContainerByHashTree_h
 
// Inclusions
#include <iostream>
#include "DGtal/base/Common.h"
#include "DGtal/base/CLabel.h"
#include "DGtal/base/ConstRangeAdapter.h"
#include "DGtal/images/DefaultConstImageRange.h"
#include "DGtal/images/DefaultImageRange.h"
 
#include "DGtal/kernel/domains/CDomain.h"
#include "DGtal/kernel/domains/HyperRectDomain.h"
#include "DGtal/kernel/SpaceND.h"
#include "DGtal/base/Bits.h"
#include "DGtal/images/Morton.h"
#include "DGtal/images/SetValueIterator.h"
#include "DGtal/io/Color.h"
#include "DGtal/base/ExpressionTemplates.h"
 
namespace DGtal
{
  namespace experimental
  {
  // template class ImageContainerByHashTree
  template < typename TDomain, typename TValue, typename THashKey = typename DGtal::uint64_t >
  class ImageContainerByHashTree
  {
 
  protected:
    class Node;
 
 
  public:
 
    typedef ImageContainerByHashTree<TDomain, TValue, THashKey> Self;
 
    typedef THashKey HashKey;
 
    BOOST_CONCEPT_ASSERT(( concepts::CDomain<TDomain> ));
    typedef TDomain Domain;
    typedef typename Domain::Point Point;
    typedef typename Domain::Vector Vector;
    typedef typename Domain::Integer Integer;
    typedef typename Domain::Size Size;
    typedef typename Domain::Dimension Dimension;
    typedef Point Vertex;
 
    BOOST_STATIC_CONSTANT( Dimension, dimension = Domain::dimension); 
    BOOST_STATIC_CONSTANT( Dimension, dim = Domain::dimension);
    typedef POW<2, dimension> PowHelper;  
    BOOST_STATIC_CONSTANT( unsigned int, NbChildrenPerNode = PowHelper::VALUE); 
    BOOST_STATIC_CONSTANT( HashKey, ROOT_KEY = static_cast<THashKey>(1)); 
 
    //(since constructed from two points as a bounding box)
    BOOST_STATIC_ASSERT ((boost::is_same< Domain,
                                          HyperRectDomain<typename Domain::Space > >::value));
 
  BOOST_CONCEPT_ASSERT(( concepts::CLabel<TValue> ));
    typedef TValue Value;
    //typedef ConstRangeAdapter<typename Domain::ConstIterator, Self, Value > ConstRange;
    typedef DefaultConstImageRange<Self> ConstRange;
    typedef DefaultImageRange<Self> Range;
 
    typedef SetValueIterator<Self> OutputIterator;
 
 
 
    ImageContainerByHashTree(const unsigned int hashKeySize,
                             const unsigned int depth,
                             const Value defaultValue);
 
    ImageContainerByHashTree(const unsigned int hashKeySize,
                             const Point & p1,
                             const Point & p2,
                             const Value defaultValue);
 
    ImageContainerByHashTree(const Domain &aDomain,
                             const unsigned int hashKeySize = 3,
                             const Value defaultValue= NumberTraits<Value>::ZERO);
 
 
    // TODO
    // /*
    //  * Copy contructor.
    //  *
    //  * @param other object to copy.
    //  */
    // ImageContainerByHashTree(const ImageContainerByHashTree<Domain, Value>& other);
 
    // /*
    //  * Assignment.
    //  *
    //  * @param other object to copy.
    //  */
    // ImageContainerByHashTree(const ImageContainerByHashTree<Domain, Value>& other);
 
    // /*
    //  * Destructor
    //  * Free the memory allocated by @a myData
    //  */
    // ~ImageContainerByHashTree();
 
 
    const Domain &domain() const;
 
    ConstRange constRange() const;
 
    Range range() ;
 
    const Self & container() const { return *this; };
    Self & container() { return *this; };
 
    const Node** & data() const noexcept { return myData; };
    Node** & data() noexcept { return myData; };
 
    Value get(const HashKey key) const;
 
 
    Value operator () (const HashKey key) const;
 
    Value operator()(const Point &aPoint) const;
 
    Value get(const Point & aPoint) const;
 
 
    Value upwardGet(const HashKey key) const ;
 
    Value reverseGet(const HashKey key) const;
 
 
    void setValue(const HashKey key, const Value object);
 
    void setValue(const Point& aPoint, const Value object);
 
    inline unsigned int getSpanSize() const
    {
      return mySpanSize;
    }
 
    inline unsigned int getDepth() const
    {
      return myTreeDepth;
    }
 
    bool isKeyValid(HashKey key) const;
 
    bool checkIntegrity(HashKey key = ROOT_KEY, bool leafAbove = false) const;
 
    int myDebugCounter; //debug
 
    //stuff that might be moved out of the class for reusability
    HashKey getKey(const Point & aPoint) const;
 
    unsigned int getKeyDepth(HashKey key) const;
 
    int* getCoordinatesFromKey(HashKey key) const;
 
    void printState(std::ostream& out, bool displayKeys = false) const;
 
    void printTree(HashKey key, std::ostream& out, bool displayKeys) const;
 
    void printInternalState(std::ostream& out, unsigned int nbBits = 0) const;
 
    void printInfo(std::ostream& out) const;
 
    unsigned int getNbEmptyLists() const;
 
    double getAverageCollisions() const;
 
    unsigned int getMaxCollisions() const;
 
    unsigned int getNbNodes(unsigned int intermediateKey) const;
 
    unsigned int getNbNodes()const;
 
 
    // -------------------------------------------------------------
    class Iterator
    {
    public:
      Iterator(Node** data, unsigned int position, unsigned int arraySize)
      {
        myArraySize = arraySize;
        myContainerData = data;
        myNode = data[0];
        myCurrentCell = position;
        while ((!myNode) && (myCurrentCell < myArraySize))
          {
            myNode = myContainerData[++myCurrentCell];
          }
      }
      bool isAtEnd()const
      {
        return myCurrentCell >= myArraySize;
      }
      Value& operator*()
      {
        return myNode->getObject();
      }
      bool operator ++ ()
      {
        return next();
      }
      bool operator == (const Iterator& it)
      {
        if (isAtEnd() && it.isAtEnd())
          return true;
        else
          return (myNode == it.myNode);
      }
      bool operator != (const Iterator& it)
      {
        if (isAtEnd() && it.isAtEnd())
          return false;
        else
          return (myNode != it.myNode);
      }
      inline HashKey getKey() const
      {
        return myNode->getKey();
      }
      bool next();
    protected:
      Node* myNode;
      unsigned int myCurrentCell;
      unsigned int myArraySize;
      Node** myContainerData;
    };
 
    Iterator begin()
    {
      return Iterator(myData, 0, myArraySize);
    }
 
    Iterator end()
    {
      return Iterator(myData, myArraySize, myArraySize);
    }
 
    void selfDisplay(std::ostream & out) const;
 
    bool isValid() const
    {
      return checkIntegrity();
    }
 
    // ------------- realization CDrawableWithBoard2D --------------------
  private:
 
 
  public:
    //DrawableWithBoard2D* defaultStyle() const;
 
    std::string className() const;
 
  protected:
 
    template <typename C>
    void
    recursiveDraw(HashKey key, const double p1[2], const double len, Board2D & board, const C& cmap) const;
 
 
    // -------------------------------------------------------------
    class Node
    {
    public:
 
      Node(Value aValue, HashKey key)
      {
        myData = aValue;
        myKey = key;
      }
 
      inline Node* getNext()
      {
        return myNext;
      }
 
 
      inline void setNext(Node* next)
      {
        myNext = next;
      }
 
      inline HashKey getKey()
      {
        return myKey;
      }
 
      inline Value& getObject()
      {
        return myData;
      }
      ~Node() { }
    protected:
      HashKey myKey;
      Node* myNext;
      Value myData;
    };// -----------------------------------------------------------
 
 
    inline HashKey getIntermediateKey(const HashKey key) const;
 
 
    Node* addNode(const Value object, const HashKey key)
    {
      Node* n = getNode(key);
      if (n)
        {
          n->getObject() = object;
          //n->setObject(object);
          return n;
        }
      n = new Node(object, key);
      HashKey key2 = getIntermediateKey(key);
      n->setNext(myData[key2]);
      myData[key2] = n;
      return n;
    }
 
  public:
    inline Node* getNode(const HashKey key)  const  // very used !! // public because Display2DFactory !!!
    {
      Node* iter = myData[getIntermediateKey(key)];
      while (iter != 0)
        {
          if (iter->getKey() == key)
            return iter;
          iter = iter->getNext();
        }
      return 0;
    }
  protected:
 
    bool removeNode(HashKey key);
 
    void recursiveRemoveNode(HashKey key, unsigned int nbRecursions);
 
 
    void setDepth(unsigned int depth);
 
    Value blendChildren(HashKey key) const;
 
 
    //----------------------- internal data --------------------------------
  protected:
 
    Domain myDomain;
 
    Node** myData;
 
    unsigned int myKeySize;
 
    unsigned int myArraySize;
 
    unsigned int myTreeDepth;
 
    unsigned int mySpanSize;
 
 
    // myN is number of children per node.
    BOOST_STATIC_CONSTANT( unsigned int, myN = NbChildrenPerNode );
 
 
  public:
    Point myOrigin; // public because Display2DFactory !!!
  protected:
 
    HashKey myDepthMask;
    HashKey myPreComputedIntermediateMask; // ~((~0) << _keySize)
 
  public:
    Morton<HashKey, Point> myMorton; // public because Display2DFactory !!!
 
 
  };
 
  template<typename TDomain, typename TValue, typename THashKey >
  std::ostream&
  operator<< ( std::ostream & out,  const ImageContainerByHashTree<TDomain, TValue, THashKey> & object )
  {
    object.selfDisplay( out);
    return out;
  }
 
 
}
} // namespace DGtal
 
// Includes inline functions.
#include "DGtal/images/ImageContainerByHashTree.ih"
 
//                                                                           //
 
#endif // !defined ImageContainerByHashTree_h
 
#undef ImageContainerByHashTree_RECURSES
#endif // else defined(ImageContainerByHashTree_RECURSES)