Salome HOME
23418: [OCC] Mesh: Minimization of memory usage of SMESH
[modules/smesh.git] / 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.upper_bound( theIndex );
270     set_iterator     r = rNext - 1;
271     int          rSize = Size( r ); // range size
272     attr_t      rValue = r->myValue;
273     if ( rValue == theValue )
274       return rValue; // it happens while compacting
275
276     if ( r->my1st == theIndex ) // theIndex is the first in the range
277     {
278       bool joinPrev = // can join theIndex to the previous range
279         ( r->my1st > 0 && ( r-1 )->myValue == theValue );
280
281       if ( rSize == 1 )
282       {
283         bool joinNext = // can join to the next range
284           ( rNext != mySet.end() && rNext->myValue == theValue );
285
286         if ( joinPrev )
287         {
288           if ( joinNext ) // && joinPrev
289           {
290             mySet.erase( r, r + 2 );
291           }
292           else // joinPrev && !joinNext
293           {
294             mySet.erase( r );
295           }
296         }
297         else
298         {
299           if ( joinNext ) // && !joinPrev
300           {
301             r = mySet.erase( r ); // then r points to the next range
302             First( r )--;
303           }
304           else // !joinPrev && !joinNext
305           {
306             const_cast< attr_t & >( r->myValue ) = theValue;
307           }
308         }
309       }
310       else // if rSize > 1
311       {
312         if ( joinPrev )
313         {
314           First( r )++;
315         }
316         else
317         {
318           r = mySet.insert( r, RANGE( theIndex + 1, rValue )) - 1;
319           const_cast< attr_t & >( r->myValue ) = theValue;
320         }
321       }
322     }
323     else if ( r->my1st + rSize - 1 == theIndex ) // theIndex is last in the range
324     {
325       if ( rNext != mySet.end() && rNext->myValue == theValue ) // join to the next
326       {
327         First( rNext )--;
328       }
329       else
330       {
331         mySet.insert( r, RANGE( theIndex, theValue ));
332       }
333     }
334     else // theIndex in the middle of the range
335     {
336       r = mySet.insert( r, RANGE( theIndex,     theValue ));
337       r = mySet.insert( r, RANGE( theIndex + 1, rValue ));
338     }
339     return rValue;
340   }
341 }; // struct _RangeSet
342
343
344 typedef _Range< int >  _ShapeIDRange; // sub-mesh ID range
345 typedef _Range< bool > _UsedRange;    // range of used elements
346
347 typedef _RangeSet< _ShapeIDRange > TSubIDRangeSet;
348 typedef _RangeSet< _UsedRange >    TUsedRangeSet;
349 typedef boost::dynamic_bitset<>    TBitSet;
350 typedef float                       TParam;
351
352 //------------------------------------------------------------------------------------
353 /*!
354  * \brief Allocate SMDS_MeshElement's (SMDS_MeshCell's or SMDS_MeshNode's )
355  *        and bind some attributes to elements:
356  *        element ID, sub-shape ID, isMarked flag, parameters on shape
357  */
358 class SMDS_ElementChunk
359 {
360   SMDS_ElementFactory* myFactory;     // holder of this chunk
361   SMDS_MeshElement*    myElements;    // array of elements
362   int                  my1stID;       // ID of myElements[0]
363   TBitSet              myMarkedSet;   // mark some elements
364   TUsedRangeSet        myUsedRanges;  // ranges of used/unused elements
365   TSubIDRangeSet       mySubIDRanges; // ranges of elements on the same sub-shape
366   int                  myMinSubID;    // min sub-shape ID
367   int                  myMaxSubID;    // max sub-shape ID
368   std::vector<TParam>  myPositions;   // UV parameters on shape: 2*param_t per an element
369
370 public:
371
372   SMDS_ElementChunk( SMDS_ElementFactory* factory = 0, int id0 = 0 );
373   ~SMDS_ElementChunk();
374
375   //! Return an element by an index [0,ChunkSize()]
376   SMDS_MeshElement* Element(int index) { return & myElements[index]; }
377
378   //! Return an element by an index [0,ChunkSize()]
379   const SMDS_MeshElement* Element(int index) const { return & myElements[index]; }
380
381   //! Return ID of the first non-used element
382   int  GetUnusedID() const;
383
384   //! Mark an element as used
385   void UseElement( const int index );
386
387   //! Mark an element as non-used
388   void Free( const SMDS_MeshElement* e );
389
390   //! Check if a given range holds used or non-used elements
391   static bool IsUsed( const _UsedRange& r ) { return r.myValue; }
392
393   //! Return index of an element in the chunk
394   int Index( const SMDS_MeshElement* e ) const { return e - myElements; }
395
396   //! Return ID of the 1st element in the chunk
397   int Get1stID() const { return my1stID; }
398
399   //! Return pointer to on-shape-parameters of a node
400   TParam* GetPositionPtr( const SMDS_MeshElement* node, bool allocate=false );
401
402   //! Return ranges of used/non-used elements
403   const TUsedRangeSet&  GetUsedRanges() const { return myUsedRanges; }
404   const TUsedRangeSet&  GetUsedRangesMinMax( bool& min, bool& max ) const
405   { min = false; max = true; return myUsedRanges; }
406
407   //! Return ranges of elements assigned to sub-shapes and min/max of sub-shape IDs
408   const TSubIDRangeSet& GetSubIDRangesMinMax( int& min, int& max ) const
409   { min = myMinSubID; max = myMaxSubID; return mySubIDRanges; }
410
411   //! Minimize allocated memory
412   void Compact();
413
414   //! Print some data
415   void Dump() const; // debug
416
417
418   // Methods called by SMDS_MeshElement
419
420   int  GetID( const SMDS_MeshElement* e ) const;
421
422   int  GetVtkID( const SMDS_MeshElement* e ) const;
423   void SetVTKID( const SMDS_MeshElement* e, const vtkIdType id );
424
425   int  GetShapeID( const SMDS_MeshElement* e ) const;
426   void SetShapeID( const SMDS_MeshElement* e, int shapeID ) const;
427
428   bool IsMarked   ( const SMDS_MeshElement* e ) const;
429   void SetIsMarked( const SMDS_MeshElement* e, bool is );
430
431   SMDS_PositionPtr GetPosition( const SMDS_MeshNode* n ) const;
432   void SetPosition( const SMDS_MeshNode* n, const SMDS_PositionPtr& pos, int shapeID );
433
434   SMDS_Mesh* GetMesh() { return myFactory->myMesh; }
435 };
436
437 //------------------------------------------------------------------------------------
438 /*!
439  * \brief Iterator on elements in chunks
440  */
441 template< class ELEM_ITERATOR, class RANGE_SET >
442 struct _ChunkIterator : public ELEM_ITERATOR
443 {
444   typedef typename ELEM_ITERATOR::value_type    element_type;
445   typedef SMDS_MeshElement::Filter*             filter_ptr;
446   typedef typename RANGE_SET::attr_t            attr_type;
447   typedef const RANGE_SET& (SMDS_ElementChunk::*get_rangeset_fun)(attr_type&, attr_type&) const;
448
449   const SMDS_MeshElement* myElement;
450   TIndexRanges            myRanges;
451   int                     myRangeIndex;
452   const TChunkVector&     myChunks;
453   int                     myChunkIndex;
454   get_rangeset_fun        myGetRangeSetFun;
455   attr_type               myValue;
456   attr_type               myMinValue;
457   attr_type               myMaxValue;
458   filter_ptr              myFilter;
459   size_t                  myNbElemsToReturn;
460   size_t                  myNbReturned;
461
462   _ChunkIterator( const TChunkVector &      theChunks,
463                   get_rangeset_fun          theGetRangeSetFun,
464                   attr_type                 theAttrValue,
465                   SMDS_MeshElement::Filter* theFilter,
466                   size_t                    theNbElemsToReturn = -1):
467     myElement( 0 ),
468     myRangeIndex( 0 ),
469     myChunks( theChunks ),
470     myChunkIndex( -1 ),
471     myGetRangeSetFun( theGetRangeSetFun ),
472     myValue( theAttrValue ),
473     myFilter( theFilter ),
474     myNbElemsToReturn( theNbElemsToReturn ),
475     myNbReturned( 0 )
476   {
477     next();
478   }
479   ~_ChunkIterator()
480   {
481     delete myFilter;
482   }
483
484   virtual bool more()
485   {
486     return myElement;
487   }
488
489   virtual element_type next()
490   {
491     element_type result = (element_type) myElement;
492     myNbReturned += bool( result );
493
494     myElement = 0;
495     if ( myNbReturned < myNbElemsToReturn )
496       while ( ! nextInRange() )
497       {
498         if ( ++myRangeIndex >= (int)myRanges.size() )
499         {
500           myRanges.clear();
501           myRangeIndex = 0;
502           while ( ++myChunkIndex < (int)myChunks.size() &&
503                   !getRangeSet().GetIndices( myValue, myRanges, &myMinValue, &myMaxValue ))
504             ;
505           if ( myChunkIndex >= (int)myChunks.size() )
506             break;
507         }
508       }
509     return result;
510   }
511
512   bool nextInRange()
513   {
514     if ( myRangeIndex < (int)myRanges.size() )
515     {
516       std::pair< int, int > & range = myRanges[ myRangeIndex ];
517       while ( range.first < range.second && !myElement )
518       {
519         myElement = myChunks[ myChunkIndex ].Element( range.first++ );
520         if ( !(*myFilter)( myElement ))
521           myElement = 0;
522       }
523     }
524     return myElement;
525   }
526
527   const RANGE_SET& getRangeSet()
528   {
529     return ( myChunks[  myChunkIndex ].*myGetRangeSetFun )( myMinValue, myMaxValue );
530   }
531 }; // struct _ChunkIterator
532
533
534 template< class ElemIterator >
535 boost::shared_ptr< ElemIterator >
536 SMDS_ElementFactory::GetIterator( SMDS_MeshElement::Filter* filter,
537                                   size_t                    nbElemsToReturn )
538 {
539   typedef _ChunkIterator< ElemIterator, TUsedRangeSet > TChuckIterator;
540   return boost::make_shared< TChuckIterator >( myChunks,
541                                                & SMDS_ElementChunk::GetUsedRangesMinMax,
542                                                /*isUsed=*/true,
543                                                filter,
544                                                nbElemsToReturn );
545 }
546
547 template< class ElemIterator >
548 boost::shared_ptr< ElemIterator >
549 SMDS_ElementFactory::GetShapeIterator( int shapeID, size_t nbElemsToReturn )
550 {
551   typedef _ChunkIterator< ElemIterator, TSubIDRangeSet > TChuckIterator;
552   return boost::make_shared< TChuckIterator >( myChunks,
553                                                & SMDS_ElementChunk::GetSubIDRangesMinMax,
554                                                /*shapeID=*/shapeID,
555                                                new SMDS_MeshElement::NonNullFilter(),
556                                                nbElemsToReturn );
557 }
558
559 #endif