src/SMDS/SMDS_ElementFactory.hxx

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