TreeNode.h

Go to the documentation of this file.

#ifndef _TREENODE_H_
#define _TREENODE_H_

#include "octUtils.h"
#include "Point.h"
#include <iostream>

#ifdef __DEBUG__
#ifndef __DEBUG_TN__
#define __DEBUG_TN__
#endif
#endif

namespace ot {

  class TreeNode {
    protected:
      //Level is also used as a flag.
      unsigned int m_uiX, m_uiY, m_uiZ, m_uiLevel, m_uiWeight, m_uiDim, m_uiMaxDepth;      
      //constructor without checks: only for faster construction.
      TreeNode (const int dummy, const unsigned int x,const unsigned int y,
          const unsigned int z,const unsigned int level, const unsigned int dim,
          const unsigned int maxDepth);

    public:

      enum BoundaryType1 { NEGATIVE= 2, POSITIVE= 4};

      enum BoundaryType2 {
        X_NEG_BDY=1, Y_NEG_BDY=2, Z_NEG_BDY=4, NEG_POS_DEMARCATION=8, 
        EXTERNAL_BDY=16, X_POS_BDY=32, Y_POS_BDY=64, Z_POS_BDY=128
      };

      enum BoundaryType3 {
        FACE_BDY=1, EDGE_BDY=2, CORNER_BDY=3
      };

      enum OctantFlagType {
       MAX_LEVEL=31, BOUNDARY=64, NODE=128 
      };

      int addBalancingDescendants(TreeNode other, std::vector<TreeNode> &seeds,
          bool incCorners) const;

      int balanceSubtree(std::vector<TreeNode > & in, std::vector<TreeNode > & out,
          bool incCorners, bool isSortedCompleteLinear) const;      

      int completeSubtree(std::vector<TreeNode > & in, std::vector<TreeNode > & out) const;

      int pickInternalBoundaryCells(std::vector<TreeNode >& in, std::vector<TreeNode > & out) const;      

      int splitInternalAndBoundaryCells(std::vector<TreeNode> & allInternal,
          std::vector<TreeNode> & onlyInternal,std::vector<TreeNode> & boundary) const;


      TreeNode (const unsigned int dim, const unsigned int maxDepth);

      TreeNode (const unsigned int x,const unsigned int y,const unsigned int z,
          const unsigned int level, const unsigned int dim, const unsigned int maxDepth);

      TreeNode (const TreeNode & other);

      TreeNode ();


      TreeNode & operator = (TreeNode const  & other);

      bool  operator == ( TreeNode const  &other) const;

      bool  operator != (TreeNode const  &other) const;

      bool  operator < ( TreeNode const  &other) const;

      bool  operator > ( TreeNode const  &other) const;

      bool  operator <= ( TreeNode const  &other) const;

      bool  operator >= ( TreeNode const  &other) const;

      friend std::ostream & operator << (std::ostream & os,TreeNode const & node) ;  

      unsigned int getDim() const;
      unsigned int getMaxDepth() const;
      unsigned int getWeight() const;
      unsigned int getLevel() const;
      unsigned int getFlag() const;
      unsigned int getX() const;
      unsigned int getY() const;
      unsigned int getZ() const;
      int getAnchor(unsigned int &x, unsigned int&y, unsigned int&z) const;
      Point getAnchor() const { return Point(m_uiX, m_uiY, m_uiZ); };
      unsigned int getParentX() const;
      unsigned int getParentY() const;
      unsigned int getParentZ() const;    
      unsigned char getChildNumber() const;
      int setWeight(unsigned int w);
      int addWeight(unsigned int w);
      int setFlag(unsigned int w);
      int orFlag(unsigned int w);

      bool isAncestor(const TreeNode & other) const;

      bool isBoundaryOctant(int type=POSITIVE, unsigned char *flags=NULL) const;

      bool isBoundaryOctant(const TreeNode &block, int type=POSITIVE, unsigned char *flags=NULL) const;

      int addChildren(std::vector<TreeNode > &list) const;

      int addBrothers(std::vector<TreeNode>&brothers) const;

      TreeNode  getParent() const;

      TreeNode  getAncestor(unsigned int ancLev) const;

      TreeNode getDFD() const;

      TreeNode getDLD() const;

      std::vector<bool> getMorton() const;

      unsigned int minX() const;
      unsigned int minY() const;
      unsigned int minZ() const;
      unsigned int maxX() const;
      unsigned int maxY() const;
      unsigned int maxZ() const;

      std::vector<TreeNode> getSearchKeys(bool incCorners);

      TreeNode  getLeft() const;
      TreeNode  getRight() const;
      TreeNode  getTop() const;
      TreeNode  getBottom() const;
      TreeNode  getFront() const;
      TreeNode  getBack() const; 
      TreeNode  getTopLeft() const;
      TreeNode  getTopRight() const;
      TreeNode  getBottomLeft() const; 
      TreeNode  getBottomRight() const;
      TreeNode  getLeftFront() const;
      TreeNode  getRightFront() const;
      TreeNode  getTopFront() const;
      TreeNode  getBottomFront() const;
      TreeNode  getTopLeftFront() const;
      TreeNode  getTopRightFront() const;
      TreeNode  getBottomLeftFront() const;
      TreeNode  getBottomRightFront() const;
      TreeNode  getLeftBack() const;
      TreeNode  getRightBack() const;
      TreeNode  getTopBack() const;
      TreeNode  getBottomBack() const;
      TreeNode  getTopLeftBack() const;
      TreeNode  getTopRightBack() const;
      TreeNode  getBottomLeftBack() const;
      TreeNode  getBottomRightBack() const;
      std::vector<TreeNode> getAllNeighbours() const;

      std::vector<TreeNode > getB_Left() const;
      std::vector<TreeNode > getB_Right() const;
      std::vector<TreeNode > getB_Top() const;
      std::vector<TreeNode > getB_Bottom() const;
      std::vector<TreeNode > getB_Front() const;
      std::vector<TreeNode > getB_Back() const; 
      std::vector<TreeNode > getB_TopLeft() const;
      std::vector<TreeNode > getB_TopRight() const;
      std::vector<TreeNode > getB_BottomLeft() const; 
      std::vector<TreeNode > getB_BottomRight() const;
      std::vector<TreeNode > getB_LeftFront() const;
      std::vector<TreeNode > getB_RightFront() const;
      std::vector<TreeNode > getB_TopFront() const;
      std::vector<TreeNode > getB_BottomFront() const;
      std::vector<TreeNode > getB_TopLeftFront() const;
      std::vector<TreeNode > getB_TopRightFront() const;
      std::vector<TreeNode > getB_BottomLeftFront() const;
      std::vector<TreeNode > getB_BottomRightFront() const;
      std::vector<TreeNode > getB_LeftBack() const;
      std::vector<TreeNode > getB_RightBack() const;
      std::vector<TreeNode > getB_TopBack() const;
      std::vector<TreeNode > getB_BottomBack() const;
      std::vector<TreeNode > getB_TopLeftBack() const;
      std::vector<TreeNode > getB_TopRightBack() const;
      std::vector<TreeNode > getB_BottomLeftBack() const;
      std::vector<TreeNode > getB_BottomRightBack() const;
      std::vector<std::vector<TreeNode> > getAllB_Neighbours() const;

  };//end of the class definition.

}//end namespace

#include "TreeNode.txx"

namespace par {

  //Forward Declaration
  template <typename T>
    class Mpi_datatype;

  template <>
    class Mpi_datatype< ot::TreeNode > {

      static void Node_MAX_LEVEL(void *in, void *inout, int* len, MPI_Datatype * dptr) {
        for(int i = 0; i < (*len); i++) {
          ot::TreeNode first = (static_cast<ot::TreeNode*>(in))[i];
          ot::TreeNode second = (static_cast<ot::TreeNode*>(inout))[i];
          (static_cast<ot::TreeNode*>(inout))[i] =
            ( ( (first.getLevel()) > (second.getLevel()) )? first : second );
        }//end for      
      }//end function

      static void Node_MAX(void *in, void *inout, int* len, MPI_Datatype * dptr) {
        for(int i = 0; i < (*len); i++) {
          ot::TreeNode first = (static_cast<ot::TreeNode*>(in))[i];
          ot::TreeNode second = (static_cast<ot::TreeNode*>(inout))[i];
          (static_cast<ot::TreeNode*>(inout))[i] = ( ( first > second )? first : second );
        }//end for      
      }//end function

      static void Node_MIN(void *in, void *inout, int* len, MPI_Datatype * dptr) {
        for(int i = 0; i < (*len); i++) {
          ot::TreeNode first = (static_cast<ot::TreeNode*>(in))[i];
          ot::TreeNode second = (static_cast<ot::TreeNode*>(inout))[i];
          (static_cast<ot::TreeNode*>(inout))[i] = ( ( first < second )? first : second );
        }//end for      
      }//end function

      static void Node_NCA(void *in, void *inout, int* len, MPI_Datatype * dptr) {
        for(int i = 0; i < (*len); i++) {
          ot::TreeNode first = (static_cast<ot::TreeNode*>(in))[i];
          ot::TreeNode second = (static_cast<ot::TreeNode*>(inout))[i];
          if( first != second ) {
            (static_cast<ot::TreeNode*>(inout))[i] = ot::getNCA(first, second);
          }//end if
        }//end for      
      }//end function

      public:
      static MPI_Op MAX_LEVEL() {
        static bool         first = true;
        static MPI_Op maxLev;
        if (first) {
          first = false;
          MPI_Op_create(Mpi_datatype<ot::TreeNode>::Node_MAX_LEVEL ,true ,&maxLev);
        }
        return maxLev;
      }

      static MPI_Op _MAX() {
        static bool         first = true;
        static MPI_Op max;
        if (first) {
          first = false;
          MPI_Op_create(Mpi_datatype<ot::TreeNode>::Node_MAX ,true ,&max);
        }
        return max;
      }

      static MPI_Op _MIN() {
        static bool         first = true;
        static MPI_Op min;
        if (first) {
          first = false;
          MPI_Op_create(Mpi_datatype<ot::TreeNode>::Node_MIN ,true ,&min);
        }
        return min;
      }

      static MPI_Op NCA() {
        static bool         first = true;
        static MPI_Op nca;
        if (first) {
          first = false;
          MPI_Op_create(Mpi_datatype<ot::TreeNode>::Node_NCA ,true ,&nca);
        }
        return nca;
      }

      static MPI_Datatype value()
      {
        static bool         first = true;
        static MPI_Datatype datatype;

        if (first)
        {
          first = false;
          MPI_Type_contiguous(sizeof(ot::TreeNode), MPI_BYTE, &datatype);
          MPI_Type_commit(&datatype);
        }

        return datatype;
      }

    };

}//end namespace par

#endif /*NODE_H_*/

---