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
  34 //================================================================================
  35
  36 //! Data limiting the tree height
  37 struct HYDROData_TreeLimit
  38 {
  39   int myMaxLevel; //!<MaxLevel of the Tree
  40   double myMinBoxSize; //!< Minimal size of the Box
  41
  42   /*! \brief Constructor with default values
  43    *
  44    * maxLevel-> 8^8 = 16777216 terminal trees at most
  45    * minSize -> 0 : box size not checked
  46    */
  47   HYDROData_TreeLimit(int maxLevel = 8, double minSize = 0.) :
  48       myMaxLevel(maxLevel), myMinBoxSize(minSize)
  49   {
  50   }
  51
  52   virtual ~HYDROData_TreeLimit()
  53   {
  54   } //!< virtual destructor can be inherited
  55 };
  56
  57 //================================================================================
  58
  59 /*!
  60  * \brief Base class for 2D and 3D trees
  61  */
  62 template<class BND_BOX, int NB_CHILDREN>
  63 class HYDROData_Tree
  64 {
  65 public:
  66
  67   typedef BND_BOX box_type;
  68
  69   //! Constructor. limit must be provided at tree root construction.
  70   //! limit will be deleted by HYDROData_Tree
  71   HYDROData_Tree(HYDROData_TreeLimit* limit = 0);
  72
  73   //! Destructor
  74   virtual ~HYDROData_Tree();
  75
  76   //! Compute the Tree. Must be called by constructor of inheriting class
  77   void compute();
  78
  79   //! Tell if Tree is a leaf or not.
  80   //! An inheriting class can influence it via myIsLeaf protected field
  81   bool isLeaf() const;
  82
  83   //! Return its level
  84   int level() const
  85   {
  86     return myLevel;
  87   }
  88
  89   //! Return Bounding Box of the Tree
  90   const box_type* getBox() const
  91   {
  92     return myBox;
  93   }
  94
  95   //! Return height of the tree, full or from this level to top leaf
  96   int getHeight(const bool full = true) const;
  97
  98   static int nbChildren()
  99   {
 100     return NB_CHILDREN;
 101   }
 102
 103   //! Compute the biggest dimension of my box
 104   virtual double maxSize() const = 0;
 105
 106 protected:
 107   //! Return box of the whole tree
 108   virtual box_type* buildRootBox() = 0;
 109
 110   //! Allocate a child
 111   virtual HYDROData_Tree* newChild() const = 0;
 112
 113   //! Allocate a bndbox according to childIndex. childIndex is zero based
 114   virtual box_type* newChildBox(int childIndex) const = 0;
 115
 116   //! Fill in data of the children
 117   virtual void buildChildrenData() = 0;
 118
 119   //! Build the children recursively
 120   void buildChildren();
 121
 122   // --- members
 123
 124   HYDROData_Tree** myChildren; //!< Array of children
 125
 126   HYDROData_Tree* myFather; //!< Point the father, NULL for the level 0
 127
 128   const HYDROData_TreeLimit* myLimit; //!< Tree limit
 129
 130   box_type* myBox; //!< Bounding box of a tree
 131
 132   int myLevel; //!< Level of the Tree
 133
 134   bool myIsLeaf; //!< Tell us if the Tree is a leaf or not
 135 };
 136
 137 /*!
 138  * Constructor. limit must be provided at tree root construction.
 139  * limit will be deleted by HYDROData_Tree.
 140  */
 141 template<class BND_BOX, int NB_CHILDREN>
 142 HYDROData_Tree<BND_BOX, NB_CHILDREN>::HYDROData_Tree(HYDROData_TreeLimit* limit) :
 143     myChildren(0), myFather(0), myLimit(limit), myBox(0), myLevel(0), myIsLeaf(false)
 144 {
 145   //if ( !myLimit ) myLimit = new HYDROData_TreeLimit();
 146 }
 147
 148 /*!
 149  * \brief Compute the Tree
 150  */
 151 template<class BND_BOX, int NB_CHILDREN>
 152 void HYDROData_Tree<BND_BOX, NB_CHILDREN>::compute()
 153 {
 154   if (myLevel == 0)
 155     {
 156       if (!myLimit)
 157         myLimit = new HYDROData_TreeLimit();
 158       myBox = buildRootBox();
 159       if (myLimit->myMinBoxSize > 0. && maxSize() <= myLimit->myMinBoxSize)
 160         myIsLeaf = true;
 161       else
 162         buildChildren();
 163     }
 164 }
 165
 166 /*!
 167  * \brief HYDROData_Tree Destructor
 168  */
 169 template<class BND_BOX, int NB_CHILDREN>
 170 HYDROData_Tree<BND_BOX, NB_CHILDREN>::~HYDROData_Tree()
 171 {
 172   if (myChildren)
 173     {
 174       if (!isLeaf())
 175         {
 176           for (int i = 0; i < NB_CHILDREN; i++)
 177             delete myChildren[i];
 178           delete[] myChildren;
 179           myChildren = 0;
 180         }
 181     }
 182   if (myBox)
 183     delete myBox;
 184   myBox = 0;
 185   if (level() == 0)
 186     delete myLimit;
 187   myLimit = 0;
 188 }
 189
 190 /*!
 191  * \brief Build the children boxes and call buildChildrenData()
 192  */
 193 template<class BND_BOX, int NB_CHILDREN>
 194 void HYDROData_Tree<BND_BOX, NB_CHILDREN>::buildChildren()
 195 {
 196   if (isLeaf())
 197     return;
 198
 199   myChildren = new HYDROData_Tree*[NB_CHILDREN];
 200
 201   // get the whole model size
 202   double rootSize = 0;
 203     {
 204       HYDROData_Tree* root = this;
 205       while (root->myLevel > 0)
 206         root = root->myFather;
 207       rootSize = root->maxSize();
 208     }
 209
 210
 211   for (int i = 0; i < NB_CHILDREN; i++)
 212     {
 213       // The child is of the same type than its father (For instance, a HYDROData_OctreeNode)
 214       // We allocate the memory we need for the child
 215       myChildren[i] = newChild();
 216       // and we assign to him its box.
 217       myChildren[i]->myFather = this;
 218       if (myChildren[i]->myLimit)
 219         delete myChildren[i]->myLimit;
 220       myChildren[i]->myLimit = myLimit;
 221       myChildren[i]->myLevel = myLevel + 1;
 222       myChildren[i]->myBox = newChildBox(i);
 223       myChildren[i]->myBox->Enlarge(rootSize * 1e-10);
 224       if (myLimit->myMinBoxSize > 0. && myChildren[i]->maxSize() <= myLimit->myMinBoxSize)
 225         myChildren[i]->myIsLeaf = true;
 226     }
 227
 228   // --- After building the NB_CHILDREN boxes, we put the data into the children.
 229   buildChildrenData();
 230
 231   // --- After we pass to the next level of the Tree
 232   for (int i = 0; i < NB_CHILDREN ; i++) {
 233     myChildren[i]->buildChildren();
 234   }
 235
 236 }
 237
 238 /*!
 239  * \brief Tell if Tree is a leaf or not
 240  *        An inheriting class can influence it via myIsLeaf protected field
 241  */
 242 template<class BND_BOX, int NB_CHILDREN>
 243 bool HYDROData_Tree<BND_BOX, NB_CHILDREN>::isLeaf() const
 244 {
 245   return myIsLeaf || ((myLimit->myMaxLevel > 0) ? (level() >= myLimit->myMaxLevel) : false);
 246 }
 247
 248 /*!
 249  * \brief Return height of the tree, full or from this level to top leaf
 250  */
 251 template<class BND_BOX, int NB_CHILDREN>
 252 int HYDROData_Tree<BND_BOX, NB_CHILDREN>::getHeight(const bool full) const
 253 {
 254   if (full && myFather)
 255     return myFather->getHeight(true);
 256
 257   if (isLeaf())
 258     return 1;
 259
 260   int heigth = 0;
 261   for (int i = 0; i < NB_CHILDREN; i++)
 262     {
 263       int h = myChildren[i]->getHeight(false);
 264       if (h > heigth)
 265         heigth = h;
 266     }
 267   return heigth + 1;
 268 }
 269
 270 #endif