src/SMDS/SMDS_ElementFactory.hxx

   1 // Copyright (C) 2007-2016  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 //  File   : SMDS_ElementFactory.hxx
  23 //  Module : SMESH
  24 //
  25 #ifndef _SMDS_ElementFactory_HeaderFile
  26 #define _SMDS_ElementFactory_HeaderFile
  27
  28 #include "SMDS_MeshCell.hxx"
  29 #include "SMDS_Position.hxx"
  30
  31 #include <Utils_SALOME_Exception.hxx>
  32
  33 #include <boost/container/flat_set.hpp>
  34 #include <boost/dynamic_bitset.hpp>
  35 #include <boost/make_shared.hpp>
  36 #include <boost/ptr_container/ptr_vector.hpp>
  37 #include <boost/shared_ptr.hpp>
  38
  39 #include <set>
  40
  41 #include <vtkType.h>
  42
  43 class SMDS_ElementChunk;
  44 class SMDS_Mesh;
  45 class SMDS_MeshCell;
  46 class SMDS_MeshNode;
  47
  48 struct _ChunkCompare {
  49   bool operator () (const SMDS_ElementChunk* c1, const SMDS_ElementChunk* c2) const;
  50 };
  51 typedef boost::ptr_vector<SMDS_ElementChunk>       TChunkVector;
  52 typedef std::set<SMDS_ElementChunk*,_ChunkCompare> TChunkPtrSet;
  53
  54 //------------------------------------------------------------------------------------
  55 /*!
  56  * \brief Allocate SMDS_MeshElement's (SMDS_MeshCell's or SMDS_MeshNode's )
  57  *        and bind some attributes to elements:
  58  *        element ID, element VTK ID, sub-mesh ID, position on shape.
  59  *
  60  * Elements are allocated by chunks, so there are used and non-used elements
  61  */
  62 class SMDS_ElementFactory
  63 {
  64 protected:
  65   bool                     myIsNodal;          // what to allocate: nodes or cells
  66   SMDS_Mesh*               myMesh;
  67   TChunkVector             myChunks;           // array of chunks of elements
  68   TChunkPtrSet             myChunksWithUnused; // sorted chunks having unused elements
  69   std::vector< vtkIdType > myVtkIDs;           // myVtkIDs[ smdsID-1 ] == vtkID
  70   std::vector< int >       mySmdsIDs;          // mySmdsIDs[ vtkID ] == smdsID - 1
  71   int                      myNbUsedElements;   // counter of elements
  72
  73   friend class SMDS_ElementChunk;
  74
  75 public:
  76
  77   SMDS_ElementFactory( SMDS_Mesh* mesh, const bool isNodal=false );
  78   virtual ~SMDS_ElementFactory();
  79
  80   //! Return minimal ID of a non-used element
  81   int GetFreeID();
  82
  83   //! Return maximal ID of an used element
  84   int GetMaxID();
  85
  86   //! Return minimal ID of an used element
  87   int GetMinID();
  88
  89   //! Return an element by ID. NULL if the element with the given ID is already used
  90   SMDS_MeshElement* NewElement( const int id );
  91
  92   //! Return a SMDS_MeshCell by ID. NULL if the cell with the given ID is already used
  93   SMDS_MeshCell* NewCell( const int id ) { return static_cast<SMDS_MeshCell*>( NewElement( id )); }
  94
  95   //! Return an used element by ID. NULL if the element with the given ID is not yet used
  96   const SMDS_MeshElement* FindElement( const int id ) const;
  97
  98   //! Return a number of used elements
  99   int NbUsedElements() const { return myNbUsedElements; }
 100
 101   //! Return an iterator on all element filtered using a given filter.
 102   //  nbElemsToReturn is used to optimize by stopping the iteration as soon as
 103   //  all elements satisfying filtering condition encountered.
 104   template< class ElemIterator >
 105   boost::shared_ptr< ElemIterator > GetIterator( SMDS_MeshElement::Filter* filter,
 106                                                  size_t nbElemsToReturn = -1 );
 107
 108   //! Return an iterator on all element assigned to a given shape.
 109   //  nbElemsToReturn is used to optimize by stopping the iteration as soon as
 110   //  all elements assigned to the shape encountered.
 111   template< class ElemIterator >
 112   boost::shared_ptr< ElemIterator > GetShapeIterator( int shapeID, size_t nbElemsToReturn );
 113
 114   //! Mark the element as non-used
 115   void Free( const SMDS_MeshElement* );
 116
 117   //! Return an SMDS ID by a Vtk one
 118   int FromVtkToSmds( vtkIdType vtkID );
 119
 120   //! De-allocate all elements
 121   virtual void Clear();
 122
 123   //! Remove unused elements located not at the end of the last chunk.
 124   //  Minimize allocated memory
 125   virtual void Compact(std::vector<int>& idCellsOldToNew);
 126
 127   //! Return true if Compact() will change IDs of elements
 128   virtual bool CompactChangePointers();
 129
 130   //! Return a number of elements in a chunk
 131   static int ChunkSize();
 132 };
 133
 134 //------------------------------------------------------------------------------------
 135 /*!
 136  * \brief Allocate SMDS_MeshNode's
 137  */
 138 class SMDS_NodeFactory : public SMDS_ElementFactory
 139 {
 140   std::vector<char> myShapeDim; // dimension of shapes
 141
 142 public:
 143
 144   SMDS_NodeFactory( SMDS_Mesh* mesh );
 145   ~SMDS_NodeFactory();
 146
 147   //! Return a SMDS_MeshNode by ID. NULL if the node with the given ID is already used
 148   SMDS_MeshNode* NewNode( int id ) { return (SMDS_MeshNode*) NewElement(id); }
 149
 150   //! Return an used node by ID. NULL if the node with the given ID is not yet used
 151   const SMDS_MeshNode* FindNode( int id ) { return (const SMDS_MeshNode*) FindElement(id); }
 152
 153   //! Set a total number of sub-shapes in the main shape
 154   void SetNbShapes( size_t nbShapes );
 155
 156   //! Return a dimension of a shape
 157   int  GetShapeDim( int shapeID ) const;
 158
 159   //! Set a dimension of a shape
 160   void SetShapeDim( int shapeID, int dim );
 161
 162   //! De-allocate all nodes
 163   virtual void Clear();
 164
 165   //! Remove unused nodes located not at the end of the last chunk.
 166   //  Minimize allocated memory
 167   virtual void Compact(std::vector<int>& idNodesOldToNew);
 168
 169   //! Return true if Compact() will change IDs of node
 170   virtual bool CompactChangePointers();
 171 };
 172
 173 //------------------------------------------------------------------------------------
 174 /*!
 175  * \brief Range of elements in a chunk having the same attribute value
 176  */
 177 template< typename ATTR>
 178 struct _Range
 179 {
 180   typedef ATTR attr_t;
 181
 182   attr_t myValue; // common attribute value
 183   int    my1st;   // index in the chunk of the 1st element
 184   _Range( int i0 = 0, attr_t v = 0 ): myValue( v ), my1st( i0 ) {}
 185
 186   bool operator < (const _Range& other) const { return my1st < other.my1st; }
 187 };
 188
 189 typedef std::vector< std::pair< int, int > > TIndexRanges;
 190
 191 //------------------------------------------------------------------------------------
 192 /*!
 193  * \brief Sorted set of ranges
 194  */
 195 template< class RANGE >
 196 struct _RangeSet
 197 {
 198   typedef typename RANGE::attr_t              attr_t;
 199   typedef boost::container::flat_set< RANGE > set_t;
 200   typedef typename set_t::const_iterator      set_iterator;
 201
 202   set_t mySet;
 203
 204   _RangeSet() { mySet.insert( RANGE( 0, 0 )); }
 205
 206   /*!
 207    * \brief Return a number of ranges
 208    */
 209   size_t Size() const { return mySet.size(); }
 210
 211   /*!
 212    * \brief Return a mutable _Range::my1st of a range pointed by an iterator
 213    */
 214   int&   First( set_iterator rangePtr ) { return const_cast< int& >( rangePtr->my1st ); }
 215
 216   /*!
 217    * \brief Return a number of elements in a range pointed by an iterator
 218    */
 219   size_t Size( set_iterator rangePtr ) const
 220   {
 221     int next1st =
 222       ( rangePtr + 1 == mySet.end() ) ? SMDS_ElementFactory::ChunkSize() : ( rangePtr + 1 )->my1st;
 223     return next1st - rangePtr->my1st;
 224   }
 225
 226   /*!
 227    * \brief Return ranges of indices (from,to) of elements having a given value
 228    */
 229   bool GetIndices( const attr_t theValue, TIndexRanges & theIndices,
 230                    const attr_t* theMinValue = 0, const attr_t* theMaxValue = 0) const
 231   {
 232     bool isFound = false;
 233
 234     if ( sizeof( attr_t ) == sizeof( int ) && theMinValue )
 235       if ( theValue < *theMinValue || theValue > *theMaxValue )
 236         return isFound;
 237
 238     for ( set_iterator it = mySet.begin(); it < mySet.end(); ++it )
 239     {
 240       if ( it->myValue == theValue )
 241       {
 242         theIndices.push_back( std::make_pair( it->my1st, it->my1st + Size( it )));
 243         isFound = true;
 244         ++it; // the next range value differs from theValue
 245       }
 246     }
 247     return isFound;
 248   }
 249
 250   /*!
 251    * \brief Return value of an element attribute
 252    *  \param [in] theIndex - element index
 253    *  \return attr_t - attribute value
 254    */
 255   attr_t GetValue( int theIndex ) const
 256   {
 257     set_iterator r = mySet.upper_bound( theIndex ) - 1;
 258     return r->myValue;
 259   }
 260
 261   /*!
 262    * \brief Change value of an element attribute
 263    *  \param [in] theIndex - element index
 264    *  \param [in] theValue - attribute value
 265    *  \return attr_t - previous value
 266    */
 267   attr_t SetValue( int theIndex, attr_t theValue )
 268   {
 269     set_iterator rNext = mySet.end(); // case of adding elements
 270     set_iterator     r = rNext - 1;
 271     if ( r->my1st > theIndex )
 272     {
 273       rNext = mySet.upper_bound( theIndex );
 274       r     = rNext - 1;
 275     }
 276     int          rSize = Size( r ); // range size
 277     attr_t      rValue = r->myValue;
 278     if ( rValue == theValue )
 279       return rValue; // it happens while compacting
 280
 281     if ( r->my1st == theIndex ) // theIndex is the first in the range
 282     {
 283       bool joinPrev = // can join theIndex to the previous range
 284         ( r->my1st > 0 && ( r-1 )->myValue == theValue );
 285
 286       if ( rSize == 1 )
 287       {
 288         bool joinNext = // can join to the next range
 289           ( rNext != mySet.end() && rNext->myValue == theValue );
 290
 291         if ( joinPrev )
 292         {
 293           if ( joinNext ) // && joinPrev
 294           {
 295             mySet.erase( r, r + 2 );
 296           }
 297           else // joinPrev && !joinNext
 298           {
 299             mySet.erase( r );
 300           }
 301         }
 302         else
 303         {
 304           if ( joinNext ) // && !joinPrev
 305           {
 306             r = mySet.erase( r ); // then r points to the next range
 307             First( r )--;
 308           }
 309           else // !joinPrev && !joinNext
 310           {
 311             const_cast< attr_t & >( r->myValue ) = theValue;
 312           }
 313         }
 314       }
 315       else // if rSize > 1
 316       {
 317         if ( joinPrev )
 318         {
 319           First( r )++;
 320         }
 321         else
 322         {
 323           r = mySet.insert( r, RANGE( theIndex + 1, rValue )) - 1;
 324           const_cast< attr_t & >( r->myValue ) = theValue;
 325         }
 326       }
 327     }
 328     else if ( r->my1st + rSize - 1 == theIndex ) // theIndex is last in the range
 329     {
 330       if ( rNext != mySet.end() && rNext->myValue == theValue ) // join to the next
 331       {
 332         First( rNext )--;
 333       }
 334       else
 335       {
 336         mySet.insert( r, RANGE( theIndex, theValue ));
 337       }
 338     }
 339     else // theIndex in the middle of the range
 340     {
 341       r = mySet.insert( r, RANGE( theIndex,     theValue ));
 342       r = mySet.insert( r, RANGE( theIndex + 1, rValue ));
 343     }
 344     return rValue;
 345   }
 346 }; // struct _RangeSet
 347
 348
 349 typedef _Range< int >  _ShapeIDRange; // sub-mesh ID range
 350 typedef _Range< bool > _UsedRange;    // range of used elements
 351
 352 typedef _RangeSet< _ShapeIDRange > TSubIDRangeSet;
 353 typedef _RangeSet< _UsedRange >    TUsedRangeSet;
 354 typedef boost::dynamic_bitset<>    TBitSet;
 355 typedef float                       TParam;
 356
 357 //------------------------------------------------------------------------------------
 358 /*!
 359  * \brief Allocate SMDS_MeshElement's (SMDS_MeshCell's or SMDS_MeshNode's )
 360  *        and bind some attributes to elements:
 361  *        element ID, sub-shape ID, isMarked flag, parameters on shape
 362  */
 363 class SMDS_ElementChunk
 364 {
 365   SMDS_ElementFactory* myFactory;     // holder of this chunk
 366   SMDS_MeshElement*    myElements;    // array of elements
 367   int                  my1stID;       // ID of myElements[0]
 368   TBitSet              myMarkedSet;   // mark some elements
 369   TUsedRangeSet        myUsedRanges;  // ranges of used/unused elements
 370   TSubIDRangeSet       mySubIDRanges; // ranges of elements on the same sub-shape
 371   int                  myMinSubID;    // min sub-shape ID
 372   int                  myMaxSubID;    // max sub-shape ID
 373   std::vector<TParam>  myPositions;   // UV parameters on shape: 2*param_t per an element
 374
 375 public:
 376
 377   SMDS_ElementChunk( SMDS_ElementFactory* factory = 0, int id0 = 0 );
 378   ~SMDS_ElementChunk();
 379
 380   //! Return an element by an index [0,ChunkSize()]
 381   SMDS_MeshElement* Element(int index) { return & myElements[index]; }
 382
 383   //! Return an element by an index [0,ChunkSize()]
 384   const SMDS_MeshElement* Element(int index) const { return & myElements[index]; }
 385
 386   //! Return ID of the first non-used element
 387   int  GetUnusedID() const;
 388
 389   //! Mark an element as used
 390   void UseElement( const int index );
 391
 392   //! Mark an element as non-used
 393   void Free( const SMDS_MeshElement* e );
 394
 395   //! Check if a given range holds used or non-used elements
 396   static bool IsUsed( const _UsedRange& r ) { return r.myValue; }
 397
 398   //! Return index of an element in the chunk
 399   int Index( const SMDS_MeshElement* e ) const { return e - myElements; }
 400
 401   //! Return ID of the 1st element in the chunk
 402   int Get1stID() const { return my1stID; }
 403
 404   //! Return pointer to on-shape-parameters of a node
 405   TParam* GetPositionPtr( const SMDS_MeshElement* node, bool allocate=false );
 406
 407   //! Return ranges of used/non-used elements
 408   const TUsedRangeSet&  GetUsedRanges() const { return myUsedRanges; }
 409   const TUsedRangeSet&  GetUsedRangesMinMax( bool& min, bool& max ) const
 410   { min = false; max = true; return myUsedRanges; }
 411
 412   //! Return ranges of elements assigned to sub-shapes and min/max of sub-shape IDs
 413   const TSubIDRangeSet& GetSubIDRangesMinMax( int& min, int& max ) const
 414   { min = myMinSubID; max = myMaxSubID; return mySubIDRanges; }
 415
 416   //! Minimize allocated memory
 417   void Compact();
 418
 419   //! Print some data
 420   void Dump() const; // debug
 421
 422
 423   // Methods called by SMDS_MeshElement
 424
 425   int  GetID( const SMDS_MeshElement* e ) const;
 426
 427   int  GetVtkID( const SMDS_MeshElement* e ) const;
 428   void SetVTKID( const SMDS_MeshElement* e, const vtkIdType id );
 429
 430   int  GetShapeID( const SMDS_MeshElement* e ) const;
 431   void SetShapeID( const SMDS_MeshElement* e, int shapeID ) const;
 432
 433   bool IsMarked   ( const SMDS_MeshElement* e ) const;
 434   void SetIsMarked( const SMDS_MeshElement* e, bool is );
 435
 436   SMDS_PositionPtr GetPosition( const SMDS_MeshNode* n ) const;
 437   void SetPosition( const SMDS_MeshNode* n, const SMDS_PositionPtr& pos, int shapeID );
 438
 439   SMDS_Mesh* GetMesh() { return myFactory->myMesh; }
 440 };
 441
 442 //------------------------------------------------------------------------------------
 443 /*!
 444  * \brief Iterator on elements in chunks
 445  */
 446 template< class ELEM_ITERATOR, class RANGE_SET >
 447 struct _ChunkIterator : public ELEM_ITERATOR
 448 {
 449   typedef typename ELEM_ITERATOR::value_type    element_type;
 450   typedef SMDS_MeshElement::Filter*             filter_ptr;
 451   typedef typename RANGE_SET::attr_t            attr_type;
 452   typedef const RANGE_SET& (SMDS_ElementChunk::*get_rangeset_fun)(attr_type&, attr_type&) const;
 453
 454   const SMDS_MeshElement* myElement;
 455   TIndexRanges            myRanges;
 456   int                     myRangeIndex;
 457   const TChunkVector&     myChunks;
 458   int                     myChunkIndex;
 459   get_rangeset_fun        myGetRangeSetFun;
 460   attr_type               myValue;
 461   attr_type               myMinValue;
 462   attr_type               myMaxValue;
 463   filter_ptr              myFilter;
 464   size_t                  myNbElemsToReturn;
 465   size_t                  myNbReturned;
 466
 467   _ChunkIterator( const TChunkVector &      theChunks,
 468                   get_rangeset_fun          theGetRangeSetFun,
 469                   attr_type                 theAttrValue,
 470                   SMDS_MeshElement::Filter* theFilter,
 471                   size_t                    theNbElemsToReturn = -1):
 472     myElement( 0 ),
 473     myRangeIndex( 0 ),
 474     myChunks( theChunks ),
 475     myChunkIndex( -1 ),
 476     myGetRangeSetFun( theGetRangeSetFun ),
 477     myValue( theAttrValue ),
 478     myFilter( theFilter ),
 479     myNbElemsToReturn( theNbElemsToReturn ),
 480     myNbReturned( 0 )
 481   {
 482     next();
 483   }
 484   ~_ChunkIterator()
 485   {
 486     delete myFilter;
 487   }
 488
 489   virtual bool more()
 490   {
 491     return myElement;
 492   }
 493
 494   virtual element_type next()
 495   {
 496     element_type result = (element_type) myElement;
 497     myNbReturned += bool( result );
 498
 499     myElement = 0;
 500     if ( myNbReturned < myNbElemsToReturn )
 501       while ( ! nextInRange() )
 502       {
 503         if ( ++myRangeIndex >= (int)myRanges.size() )
 504         {
 505           myRanges.clear();
 506           myRangeIndex = 0;
 507           while ( ++myChunkIndex < (int)myChunks.size() &&
 508                   !getRangeSet().GetIndices( myValue, myRanges, &myMinValue, &myMaxValue ))
 509             ;
 510           if ( myChunkIndex >= (int)myChunks.size() )
 511             break;
 512         }
 513       }
 514     return result;
 515   }
 516
 517   bool nextInRange()
 518   {
 519     if ( myRangeIndex < (int)myRanges.size() )
 520     {
 521       std::pair< int, int > & range = myRanges[ myRangeIndex ];
 522       while ( range.first < range.second && !myElement )
 523       {
 524         myElement = myChunks[ myChunkIndex ].Element( range.first++ );
 525         if ( !(*myFilter)( myElement ))
 526           myElement = 0;
 527       }
 528     }
 529     return myElement;
 530   }
 531
 532   const RANGE_SET& getRangeSet()
 533   {
 534     return ( myChunks[  myChunkIndex ].*myGetRangeSetFun )( myMinValue, myMaxValue );
 535   }
 536 }; // struct _ChunkIterator
 537
 538
 539 template< class ElemIterator >
 540 boost::shared_ptr< ElemIterator >
 541 SMDS_ElementFactory::GetIterator( SMDS_MeshElement::Filter* filter,
 542                                   size_t                    nbElemsToReturn )
 543 {
 544   typedef _ChunkIterator< ElemIterator, TUsedRangeSet > TChuckIterator;
 545   return boost::make_shared< TChuckIterator >( myChunks,
 546                                                & SMDS_ElementChunk::GetUsedRangesMinMax,
 547                                                /*isUsed=*/true,
 548                                                filter,
 549                                                nbElemsToReturn );
 550 }
 551
 552 template< class ElemIterator >
 553 boost::shared_ptr< ElemIterator >
 554 SMDS_ElementFactory::GetShapeIterator( int shapeID, size_t nbElemsToReturn )
 555 {
 556   typedef _ChunkIterator< ElemIterator, TSubIDRangeSet > TChuckIterator;
 557   return boost::make_shared< TChuckIterator >( myChunks,
 558                                                & SMDS_ElementChunk::GetSubIDRangesMinMax,
 559                                                /*shapeID=*/shapeID,
 560                                                new SMDS_MeshElement::NonNullFilter(),
 561                                                nbElemsToReturn );
 562 }
 563
 564 #endif