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/kernel/domains/CDomain.h"
#include "DGtal/kernel/domains/HyperRectDomain.h"
#include "DGtal/kernel/SpaceND.h"
#include "DGtal/base/Bits.h"
//#include "DGtal/io/boards/Board2D.h"
#include "DGtal/images/Morton.h"
#include "DGtal/images/SetValueIterator.h"
#include "DGtal/io/Color.h"
#include "DGtal/base/ExpressionTemplates.h"

namespace DGtal
{
  // 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(( 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;

    static const typename Domain::Dimension dimension = Domain::dimension;
    static const typename Domain::Dimension dim = Domain::dimension;
    static const unsigned int NbChildrenPerNode = POW<2, dimension>::VALUE;
    static const HashKey ROOT_KEY = static_cast<HashKey>(1);

    //(since constructed from two points as a bounding box)
    BOOST_STATIC_ASSERT ((boost::is_same< Domain, 
                                          HyperRectDomain<SpaceND<dimension, Integer> > >::value));

    BOOST_CONCEPT_ASSERT(( CLabel<TValue> ));
    typedef TValue Value;
    typedef ConstRangeAdapter<typename Domain::ConstIterator, Self, Value > ConstRange; 

    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 range() const;

    OutputIterator outputIterator();


    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;
      
    /*
     * Prints in the state of the container as a tree. (Calls
     * printTree)
     * 
     * @param out output stream.  
     * @param displayKeys  boolean to decide if keys are displayed .
     */
    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;


    // -------------------------------------------------------------
    /*  Iterator inner-class
     *
     *  @brief Buil-in iterator on an HashTree. This iterator visits
     *  all node in the tree.
     *
     * -------------------------------------------------------------
     */
    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);

    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.
    static const unsigned int myN=POW<2,dim>::VALUE;


  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,  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)