src/HYDROData/HYDROData_Tree.hxx

   1 // Copyright (C) 2007-2014  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 // This library is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU Lesser General Public
   8 // License as published by the Free Software Foundation; either
   9 // version 2.1 of the License, or (at your option) any later version.
  10 //
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // Lesser General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Lesser General Public
  17 // License along with this library; if not, write to the Free Software
  18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22
  23 //  HYDRO HYDROData_Tree : tree implementation (from SMESH module)
  24 //  File      : HYDROData_Tree.hxx
  25 //  Created   : Tue Jan 16 16:00:00 2007
  26 //  Author    : Nicolas Geimer & Aurélien Motteux (OCC)
  27 //  Module    : HYDRO
  28 //
  29 #ifndef _HYDROData_Tree_HXX_
  30 #define _HYDROData_Tree_HXX_
  31
  32 #include <HYDROData_Tool.h>
  33 #include <Message_ProgressSentry.hxx>
  34
  35 //================================================================================
  36
  37 //! Data limiting the tree height
  38 struct HYDROData_TreeLimit
  39 {
  40   int myMaxLevel; //!<MaxLevel of the Tree
  41   double myMinBoxSize; //!< Minimal size of the Box
  42
  43   /*! \brief Constructor with default values
  44    *
  45    * maxLevel-> 8^8 = 16777216 terminal trees at most
  46    * minSize -> 0 : box size not checked
  47    */
  48   HYDROData_TreeLimit(int maxLevel = 8, double minSize = 0.) :
  49       myMaxLevel(maxLevel), myMinBoxSize(minSize)
  50   {
  51   }
  52
  53   virtual ~HYDROData_TreeLimit()
  54   {
  55   } //!< virtual destructor can be inherited
  56 };
  57
  58 //================================================================================
  59
  60 /*!
  61  * \brief Base class for 2D and 3D trees
  62  */
  63 template<class BND_BOX, int NB_CHILDREN>
  64 class HYDROData_Tree
  65 {
  66 public:
  67
  68   typedef BND_BOX box_type;
  69
  70   //! Constructor. limit must be provided at tree root construction.
  71   //! limit will be deleted by HYDROData_Tree
  72   HYDROData_Tree(HYDROData_TreeLimit* limit = 0);
  73
  74   //! Destructor
  75   virtual ~HYDROData_Tree();
  76
  77   //! Compute the Tree. Must be called by constructor of inheriting class
  78   void compute();
  79
  80   //! Tell if Tree is a leaf or not.
  81   //! An inheriting class can influence it via myIsLeaf protected field
  82   bool isLeaf() const;
  83
  84   //! Return its level
  85   int level() const
  86   {
  87     return myLevel;
  88   }
  89
  90   //! Return Bounding Box of the Tree
  91   const box_type* getBox() const
  92   {
  93     return myBox;
  94   }
  95
  96   //! Return height of the tree, full or from this level to top leaf
  97   int getHeight(const bool full = true) const;
  98
  99   static int nbChildren()
 100   {
 101     return NB_CHILDREN;
 102   }
 103
 104   //! Compute the biggest dimension of my box
 105   virtual double maxSize() const = 0;
 106
 107 protected:
 108   //! Return box of the whole tree
 109   virtual box_type* buildRootBox() = 0;
 110
 111   //! Allocate a child
 112   virtual HYDROData_Tree* newChild() const = 0;
 113
 114   //! Allocate a bndbox according to childIndex. childIndex is zero based
 115   virtual box_type* newChildBox(int childIndex) const = 0;
 116
 117   //! Fill in data of the children
 118   virtual void buildChildrenData() = 0;
 119
 120   //! Build the children recursively
 121   void buildChildren();
 122
 123   // --- members
 124
 125   HYDROData_Tree** myChildren; //!< Array of children
 126
 127   HYDROData_Tree* myFather; //!< Point the father, NULL for the level 0
 128
 129   const HYDROData_TreeLimit* myLimit; //!< Tree limit
 130
 131   box_type* myBox; //!< Bounding box of a tree
 132
 133   int myLevel; //!< Level of the Tree
 134
 135   bool myIsLeaf; //!< Tell us if the Tree is a leaf or not
 136 };
 137
 138 /*!
 139  * Constructor. limit must be provided at tree root construction.
 140  * limit will be deleted by HYDROData_Tree.
 141  */
 142 template<class BND_BOX, int NB_CHILDREN>
 143 HYDROData_Tree<BND_BOX, NB_CHILDREN>::HYDROData_Tree(HYDROData_TreeLimit* limit) :
 144     myChildren(0), myFather(0), myLimit(limit), myBox(0), myLevel(0), myIsLeaf(false)
 145 {
 146   //if ( !myLimit ) myLimit = new HYDROData_TreeLimit();
 147 }
 148
 149 /*!
 150  * \brief Compute the Tree
 151  */
 152 template<class BND_BOX, int NB_CHILDREN>
 153 void HYDROData_Tree<BND_BOX, NB_CHILDREN>::compute()
 154 {
 155   if (myLevel == 0)
 156     {
 157       if (!myLimit)
 158         myLimit = new HYDROData_TreeLimit();
 159       myBox = buildRootBox();
 160       if (myLimit->myMinBoxSize > 0. && maxSize() <= myLimit->myMinBoxSize)
 161         myIsLeaf = true;
 162       else
 163         buildChildren();
 164     }
 165 }
 166
 167 /*!
 168  * \brief HYDROData_Tree Destructor
 169  */
 170 template<class BND_BOX, int NB_CHILDREN>
 171 HYDROData_Tree<BND_BOX, NB_CHILDREN>::~HYDROData_Tree()
 172 {
 173   if (myChildren)
 174     {
 175       if (!isLeaf())
 176         {
 177           for (int i = 0; i < NB_CHILDREN; i++)
 178             delete myChildren[i];
 179           delete[] myChildren;
 180           myChildren = 0;
 181         }
 182     }
 183   if (myBox)
 184     delete myBox;
 185   myBox = 0;
 186   if (level() == 0)
 187     delete myLimit;
 188   myLimit = 0;
 189 }
 190
 191 /*!
 192  * \brief Build the children boxes and call buildChildrenData()
 193  */
 194 template<class BND_BOX, int NB_CHILDREN>
 195 void HYDROData_Tree<BND_BOX, NB_CHILDREN>::buildChildren()
 196 {
 197   if (isLeaf())
 198     return;
 199
 200   myChildren = new HYDROData_Tree*[NB_CHILDREN];
 201
 202   // get the whole model size
 203   double rootSize = 0;
 204     {
 205       HYDROData_Tree* root = this;
 206       while (root->myLevel > 0)
 207         root = root->myFather;
 208       rootSize = root->maxSize();
 209     }
 210
 211   Handle(Message_ProgressIndicator) aZIProgress = myLevel == 0 ? HYDROData_Tool::GetZIProgress() : NULL;
 212   Message_ProgressSentry aPSentry(aZIProgress, "QuadTree", 0, NB_CHILDREN + 1, 1);
 213
 214   for (int i = 0; i < NB_CHILDREN; i++)
 215     {
 216       // The child is of the same type than its father (For instance, a HYDROData_OctreeNode)
 217       // We allocate the memory we need for the child
 218       myChildren[i] = newChild();
 219       // and we assign to him its box.
 220       myChildren[i]->myFather = this;
 221       if (myChildren[i]->myLimit)
 222         delete myChildren[i]->myLimit;
 223       myChildren[i]->myLimit = myLimit;
 224       myChildren[i]->myLevel = myLevel + 1;
 225       myChildren[i]->myBox = newChildBox(i);
 226       myChildren[i]->myBox->Enlarge(rootSize * 1e-10);
 227       if (myLimit->myMinBoxSize > 0. && myChildren[i]->maxSize() <= myLimit->myMinBoxSize)
 228         myChildren[i]->myIsLeaf = true;
 229     }
 230
 231   // --- After building the NB_CHILDREN boxes, we put the data into the children.
 232   buildChildrenData();
 233
 234   if (aPSentry.More()) {
 235     aPSentry.Next();
 236   }
 237
 238   // --- After we pass to the next level of the Tree
 239   for (int i = 0; i < NB_CHILDREN && aPSentry.More(); i++, aPSentry.Next()) {
 240     myChildren[i]->buildChildren();
 241   }
 242
 243   aPSentry.Relieve();
 244 }
 245
 246 /*!
 247  * \brief Tell if Tree is a leaf or not
 248  *        An inheriting class can influence it via myIsLeaf protected field
 249  */
 250 template<class BND_BOX, int NB_CHILDREN>
 251 bool HYDROData_Tree<BND_BOX, NB_CHILDREN>::isLeaf() const
 252 {
 253   return myIsLeaf || ((myLimit->myMaxLevel > 0) ? (level() >= myLimit->myMaxLevel) : false);
 254 }
 255
 256 /*!
 257  * \brief Return height of the tree, full or from this level to top leaf
 258  */
 259 template<class BND_BOX, int NB_CHILDREN>
 260 int HYDROData_Tree<BND_BOX, NB_CHILDREN>::getHeight(const bool full) const
 261 {
 262   if (full && myFather)
 263     return myFather->getHeight(true);
 264
 265   if (isLeaf())
 266     return 1;
 267
 268   int heigth = 0;
 269   for (int i = 0; i < NB_CHILDREN; i++)
 270     {
 271       int h = myChildren[i]->getHeight(false);
 272       if (h > heigth)
 273         heigth = h;
 274     }
 275   return heigth + 1;
 276 }
 277
 278 #endif