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